Overview of knowledge points:

 

 

1. Sum of two numbers:

Given an integer array ， nums ， and an integer target value ， target, please find the ， and the ， integers with the target value ， target ， in the array and return their array subscripts.

You can assume that each input will correspond to only one answer. However, the same element in the array cannot appear repeatedly in the answer.

[example]

Input: num = [2,7,11,15], target = 9
Output: [1,0]
Explanation: because num [0] + num [1] = = 9, return [0, 1].

class Solution {//Double pointer solution
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){//Traverse from the first number
            for(int j=i+1;j<nums.length;j++){//Double pointer, traversing from the second number
                if(nums[i]+nums[j]==target)
                return new int[] {i,j};
            }
        }
        //throw new IllegalArgumentException("no two sum solution");
        return new int[] {};
    }
}

2. Sum of the nearest three numbers:

Give you an integer array with a length of ， n ， num ， and a target value ， target. Please select three integers from {num} to make their sum closest to {target}.

Returns the sum of these three numbers.

It is assumed that there is only exactly one solution for each set of inputs.

[example]

Input: num = [- 1,2,1, - 4], target = 1
 Output: 2
 Explanation: the closest sum to target is 2 (- 1 + 2 + 1 = 2).

class Solution {//Sort the array first
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int sum = 0;
        int rand = nums[0]+nums[1]+nums[2];//Sum of the first three numbers
        for(int i=0;i<nums.length;i++){//Traversal array
            int start = i+1,end = nums.length-1;//Define two pointers
            while(start<end){
                sum = nums[i]+nums[start]+nums[end];
                if(Math.abs(target-sum)<Math.abs(target-rand)) rand = sum;//Select the one with small absolute value difference from the target value
                if(sum > target) end--;//If it is greater than the target value, the last pointer moves forward
                else if(sum < target) start++;//If it is less than the target value, the header pointer moves back
                else return rand;//If it is equal to the target value, rand is returned
            }
        }
        return rand;//Finally, rand is returned
    }
}

3. Delete duplicates in the ordered array:

I'll give you an ordered array {nums, please In situ Delete the repeated elements, so that each element {only appears once, and return the new length of the deleted array.

Do not use extra array space, you must In situ Modify the array with additional space (1).

[example 1]

Input: num = [1,1,2]
Output: 2, Num = [1,2]
Explanation: the function should return a new length of 2, and the first two elements of the original array num are modified to 1 and 2. There is no need to consider the elements in the array that exceed the new length.

[example 2]

Input: num = [0,0,1,1,1,2,2,3,3,4]
Output: 5, Num = [0,1,2,3,4]
Explanation: the function should return a new length of 5, and the first five elements of the original array num are modified to 0, 1, 2, 3 and 4. There is no need to consider the elements in the array that exceed the new length.

class Solution {
    public int removeDuplicates(int[] nums) {
        int j=0;//Counter
        for(int i=0;i<nums.length;i++){//Traversal array
            if(nums[i]!=nums[j])
                nums[++j]=nums[i];
        }
        return j+1;
    }    
}

4. Remove elements:

Give you an array ， num ， and a value ， val, you need In situ Removes all elements with a value equal to val ， and returns the new length of the array after removal.

Don't use extra array space, you must only use {O(1) extra space and In situ Modify the input array.

The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.

[example]

Input: num = [3,2,2,3], Val = 3
 Output: 2, Num = [2,2]
Explanation: the function should return a new length of 2, and the first two elements in num are 2. You don't need to consider the elements in the array that exceed the new length. For example, if the new length returned by the function is 2, and num = [2,2,3,3] or num = [2,2,0,0], it will also be regarded as the correct answer.

class Solution {//
    public int removeElement(int[] nums, int val) {
        int ans =0;//Counter
        for(int num:nums){//Traverse array elements
            if(num!=val){//If it is not equal to val, put num in the current position
                nums[ans] = num;
                ans++;//Counter++
            }
        }
        return ans;//Return counter
    }
}

5. Sum of three numbers:

Give you an array of # n # integers # nums. Judge whether there are three elements # a, b and c in # nums # so that # a + b + c = 0? Please find all triples whose sum is 0 ， and are not repeated.

Note: the answer cannot contain duplicate triples.

[example]

Input: num = [- 1,0,1,2, - 1, - 4]
Output: [- 1, - 1,2], [- 1,0,1]]

class Solution {//It is similar to the two questions in the article
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                return result;
            }
            
            if(i>0&&nums[i] == nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
                while(left<right){
                    int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0) right--;
                else if(sum < 0) left++;
                else{
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    
                    while(right>left && nums[right] == nums[right-1]) right--;
                    while(right>left && nums[left] == nums[left+1]) left--;
                    
                    right--;
                    left++;
                    }
                }
        }
        return result;
    }
}