TwoPointer 🌼

双指针法将时间复杂度：O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：

链表相关双指针题目：

27. Remove Element

Easy

Example :

1
2
3
4
5
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

🌟Coding:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int flag = 0;
        for(int i = 0 ; i < nums.length; i++){
            if(nums[i] != val){
                nums[flag] = nums[i];
                flag ++;
            }
        }
        return flag;     
    }
}

344. Reverse String

Easy

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example :

1
2
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

🌟Coding:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public void reverseString(char[] s) {
        int tail = s.length - 1;
        for(int i = 0; i < s.length/2; i++){
            char temp;
            temp = s[i];
            s[i] = s[tail];
            s[tail] = temp;
            tail --;
        }     
    }
}

125.Valid Palindrome

Easy

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example :

1
2
3
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

🌟Coding:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isPalindrome(String s) {
       
        int start ;
        int end = s.length() - 1;

        for(start = 0; start <= end; ){

            if(!Character.isLetterOrDigit( s.charAt(start) )){
                start ++;
                continue;
            }
            if(!Character.isLetterOrDigit( s.charAt(end) )){
                end --;
                continue;
            }
            
            if( Character.toLowerCase( s.charAt(start)) !=  Character.toLowerCase(s.charAt(end)) ){
                return false;
            }else{
                start ++;
                end --;
            }
            
        }
        
        return true;        
    }
}

⭕ Character.isLetterOrDigit( char )

⭕ Character.toLowerCase( char )

⭕ String s -> s.length();

​ char[] s -> s.length;

⭕ char: ==

​ String: equals();

167. Two Sum II - Input Array Is Sorted

Medium

Given a 1-indexed array of integers numbers that is already *sorted in non-decreasing order*, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

1
2
3
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

🌟Coding:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        
        for (int i = 0 ; i < numbers.length; i ++){
            for(int  j = numbers.length - 1; j > i; j --){
                if (numbers[i] + numbers[j] == target)
                    return new int[] {i+1,j+1};
                if( numbers[i] + numbers[j] < target) 
               // without this if sentence then the time complexity cannot pass the test
                    break;
            }
        }

        return new int[]{0};
    }
}

⭕The break statement can be used to jump out of a loop.

​ The continue statement breaks one iteration (in the loop), if a specified condition occurs, and continues with the next iteration in the loop.

2109. Adding Spaces to a String

Medium

Example :

1
2
3
4
5
Input: s = "icodeinpython", spaces = [1,5,7,9]
Output: "i code in py thon"
Explanation:
The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython".
We then place spaces before those characters.

🌟Coding:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public String addSpaces(String s, int[] spaces) {
        int index = 0;
        StringBuilder ans = new StringBuilder();
        for(int i = 0, j = 0; i < s.length(); i++){
            if( j < spaces.length && i == spaces[j] ){
                ans.append(" ");
                j++;
                i--;
            }else{
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}



class Solution {
    public String addSpaces(String s, int[] spaces) {
        char[] ss = s.toCharArray();
        char[] res = new char[spaces.length + s.length()];
        int flag = 0;

        for(int i = 0, j =0; i < res.length; i++){
            if(j < spaces.length && spaces[j] + j == i) { //!!! notice you need to  + j here
                res[i] = ' ';
                j++;
            }else{
                res[i] = ss[flag];
                flag ++;
            }
        }

        return new String(res);
    }
}

⭕ Here we should use StringBuilder not ArrayList

⭕ Time Limit Exceeded:

if里面 i–； 最后又i++ ; i一直是一个值不变就反复跑for loop. when j > space, j would not change and i will go into an dead loop.

but for the method below, i decreases at the same time when j increase so it won’t cause infinite loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
wrong:
class Solution {
    public String addSpaces(String s, int[] spaces) {
        int index = 0;
        StringBuilder ans = new StringBuilder();
        for(int i = 0, j = 0; i < s.length(); i++){
            if( i == spaces[j] ){
                ans.append(" ");
                i--;
                if(j < spaces.length - 1)
                    j++;
                
            }else{
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}

151. Reverse Words in a String

Example :

1
2
Input: s = "the sky is blue"
Output: "blue is sky the"

Input：”the sky is blue “

  1. remove extra: “the sky is blue”

  2. reverse the whole input：”eulb si yks eht”

  3. reverse every single word：”blue is sky the”

🌟Coding:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Solution {
	//remove extra space
    public static StringBuilder removeSpace(String s){
        StringBuilder sb = new StringBuilder();
        int start = 0 ;
        int end = s.length() - 1;
        // remove all space in the front and back of the array
        while(s.charAt(start) ==(' ')) start++;
        while(s.charAt(end) ==(' ')) end--;
        //remove extra space in the middle of the array
        for(int i = start ; i <= end; i++){
            if(s.charAt(i) != ' '){
                sb.append(s.charAt(i));
            }
            if(s.charAt(i) == ' ' && s.charAt(i-1) != ' '){
                sb.append(" ");

            }
        }
        return sb;
    }
	// reverse from start to end
    public static void reverse(StringBuilder sb, int start, int end){  //notice here could be void

        while( start < end){
            char temp = sb.charAt(end);
            sb.setCharAt(end , sb.charAt(start));
            sb.setCharAt(start, temp);
            start ++;
            end --;
        }
        System.out.println(sb);
    }

   
    public String reverseWords(String s) {
        StringBuilder temp =  removeSpace(s);     
        reverse(temp, 0 , temp.length()-1);
        // reverse each single word
        int start = 0;
        int end = 1;
        int n = temp.length();
        while (start < n) {
            while (end < n && temp.charAt(end) != ' ') {
                end++;
            }
            reverse(temp, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
        System.out.println(temp);
        return temp.toString();
    }
    
//MY FIRST TRY WHICH IS WRONG
    // reverse each single word
//        int start = 0;
//        int end = 0;
//        for( int i = 0 ; i < temp.length(); i ++){
//            if(temp.charAt(i)!= ' ' ){
//                end = i; // end equals to the last charater which is right before the space
//            }
//            if(temp.charAt(i) == ' ' ){   
   			  //这里错了 可以改成if (temp.charAt(i) == ' ' || i == temp.length() - 1) 
//                reverse(temp, start, end);
//                start = i + 1; //start move to one after the end
//            }
//        }
    
}


// second try:


class Solution {

    public static String reverseWords(String s){
       String ss = reverse(s, 0, s.length() - 1);
       for(int i = 0; i < ss.length(); i++){
           
           if(ss.charAt(i) != ' '){
               int start = i;
           
           while(i < ss.length() && ss.charAt(i) != ' '){
               i++;
           }
            i --;
           ss = reverse(ss, start, Math.min(i, s.length()-1));
               
        //or  while(i+1 < ss.length() && ss.charAt(i+1) != ' '){
        //        i++;
        //    }
        
        //    ss = reverse(ss, start, Math.min(i, s.length()-1));

           }

       }

        return removeSpace(ss);
    }
    public static String removeSpace(String s){
        char[] ss = s.trim().toCharArray();
        StringBuilder sb = new StringBuilder();
        for( int i = 0 ; i < ss.length; i++){
            if(ss[i] != ' ') sb.append(ss[i]);
            if(ss[i] == ' '){
                sb.append(' ');
                while(i < s.length() && ss[i] == ' '){
                    i++;
                }
                i--;
            }
        }
        return sb.toString();
    }

    public static String reverse(String s, int start, int end){
        char[] ss = s.toCharArray();
        while (start <= end) {
            char temp = ss[start];
            ss[start] = ss[end];
            ss[end] = temp;
            start++;
            end--;
        }
        return new String(ss);
    }
}

18. 4Sum

Medium

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

1
2
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> temp = new LinkedList<>();
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        for(int i = 0; i< nums.length; i++){
            if(nums[i] > 0 && nums[i] > target) return res;
            if(i > 0 && nums[i] == nums[i -1]) continue;
            for(int j = i+1; j < nums.length; j++){
                if(j > i + 1 && nums[j] == nums[j -1]) continue;
                int left =  j + 1;
                int right = nums.length -1;
                while(right >left){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum > target){
                        right --;
                    }else if(sum < target){
                        left++;
                    }else{
                    //注意这里的去重 !!!!
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));   !!!!!!!!!
                        while(right > left && nums[right] == nums[right - 1]) right --;  // 注意这个条件right > left
                        while(right > left && nums[left] == nums[left +  1]) left ++;
                        right --;
                        left ++;
                    }

                }
            }
        }

    return res;


    // Time Limit Exceeded
    //     Arrays.sort(nums); // Sort the array to help in avoiding duplicates
    //     seek(nums, target, 0);
    //     return res;
    // }
    
    // public void seek(int[] nums, int target, int index) {
    //     if (temp.size() == 4) {
    //         int sum = 0;
    //         for (int num : temp) {
    //             sum += num;
    //         }
    //         if (sum == target) {
    //             res.add(new ArrayList<>(temp));
    //         }
    //         return;
    //     }
    //     for (int i = index; i < nums.length; i++) {
    //         if (i > index && nums[i] == nums[i - 1]) {
    //             continue; // Skip duplicates
    //         }
    //         temp.add(nums[i]);
    //         seek(nums, target, i + 1);
    //         temp.removeLast();
    //     }
    }
}

Arrays.asList

！！！！ convert an array or a set of elements into a List implementation.

15. 3Sum

Medium

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

1
2
3
4
5
6
7
8
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0) return res;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1;
            int right = nums.length - 1;
            //注意这里最开始我没有写这个while语句
            while(left < right)
           { 
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0){
                    right--;
                }else if(sum < 0){
                    left ++;
                }else{
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 注意这里的while我最开始写成了if
                    while(right>left && nums[left] == nums[left+1]) left ++;
                    while(right>left && nums[right] == nums[right-1]) right --;
                    left++;
                    right--;
                }
            }
        }

        return res;
    }
}

[toc]