Array: question brushing record

Overview of knowledge points ：

 

 

---

1. Sum of two numbers ：

Given an array of integers  nums  And an integer target value  target, Please find... In the array   And is the target value  target  the   Two   Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

【 example 】

Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .

class Solution {// Double pointer violence solution 
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){// From 1 The number starts to traverse 
            for(int j=i+1;j<nums.length;j++){// Double pointer , From 2 The number starts to traverse 
                if(nums[i]+nums[j]==target)
                return new int[] {i,j};
            }
        }
        //throw new IllegalArgumentException("no two sum solution");
        return new int[] {};
    }
}

---

2. The closest sum of three ：

Give you a length of  n  Array of integers for  nums  and A target value  target. Please start from  nums  Choose three integers , Make their sum with  target  Nearest .

Returns the sum of the three numbers .

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

【 example 】

 Input ：nums = [-1,2,1,-4], target = 1
 Output ：2
 explain ： And  target  The closest and  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];// The 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;// Choose the one with a small absolute difference from the target value 
                if(sum > target) end--;// If it is greater than the target value, the end pointer moves forward 
                else if(sum < target) start++;// Less than the target value, the header pointer moves back 
                else return rand;// If it is equal to the target value, it returns rand
            }
        }
        return rand;// Finally back to rand
    }
}

---

3. Remove duplicate items from an ordered array ：

Here's an ordered array  nums , Would you please   In situ   Delete duplicate elements , Make each element   Only once  , Returns the new length of the deleted array .

Don't use extra array space , You must be there.   In situ   Modify input array   And using O(1) Complete with extra space .

【 example 1】

 Input ：nums = [1,1,2]
 Output ：2, nums = [1,2]
 explain ： Function should return the new length  2, And the original array  nums  The first two elements of are modified to  1, 2. You don't need to think about the elements in the array that follow the new length .

【 example 2】

 Input ：nums = [0,0,1,1,1,2,2,3,3,4]
 Output ：5, nums = [0,1,2,3,4]
 explain ： Function should return the new length  5,  And the original array  nums  The first five elements of are modified to  0, 1, 2, 3, 4. You don't need to think about the elements in the array that follow 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  nums  And a value  val, You need   In situ   Remove all values equal to  val  The elements of , And return the new length of the array after removal .

Don't use extra array space , You have to use only  O(1)  Additional space and   In situ   Modify input array .

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

【 example 】

 Input ：nums = [3,2,2,3], val = 3
 Output ：2, nums = [2,2]
 explain ： Function should return the new length  2,  also  nums  The first two elements in are  2. You don't need to think about the elements in the array that follow the new length . for example , The new length returned by the function is  2 , and  nums = [2,2,3,3]  or  nums = [2,2,0,0], It will also be seen as the right answer .

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

---

5. Sum of three numbers ：

Give you one containing  n  Array of integers  nums, Judge  nums  Are there three elements in  a,b,c , bring  a + b + c = 0 ？ Please find out all and for  0  Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

【 example 】

 Input ：nums = [-1,0,1,2,-1,-4]
 Output ：[[-1,-1,2],[-1,0,1]]

class Solution {// With the article 2 Similar ideas 
    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;
    }
}