Leetcode 15: sum of three numbers

link

subject ：

Ideas ： Sort + Double pointer

nSum The core idea of a series of questions is to sort + Double pointer ;

Why can't the sum of two numbers use double pointers ？
Double pointers require array sorting , The sum of two numbers needs to return the index , After sorting, the index is messy ！

Two pointer thought ：

according to sum Resize the left and right pointers ;

however , This implementation will result in duplicate results , for instance nums = [1,1,1,2,2,3,3], target = 4, In the result [1,3] It will be repeated ;
So when nums[left] With the next number nums[left+1] Equal is equal left++ skip ,right Empathy ！

Be careful ：
Sum of three ,left Must be from i+1 Start , Otherwise, the double pointer will be used repeatedly num[i] ！

Java Realization ：

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    
        //  The number returned is not the index  ！
        List<List<Integer>> r=new ArrayList<>();
        if(nums.length==0){
    
            return r;
        }
        // 1. Prioritize 
        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++){
    
            //  duplicate removal 1
            if(i>0 && nums[i]==nums[i-1]){
    
                continue; //  Traverse to the next  i
            }
            //  If i>0, And the array is increasing , Is doomed to be unable to come up with 0 ！
			if(nums[i]>0){
    
                continue;
            }
            // 2. Double pointer found 0-nums[i] Two numbers of , 
            int target=0-nums[i];
            int left=i+1; // left Must be from i+1 Start , Otherwise, it will be reused num[i] ！
            int right=nums.length-1;
            while(left<right){
    
                int sum=nums[left]+nums[right];
                //  according to sum To adjust the pointer 
                if(sum>target){
    
                    right--;
                }else if(sum<target){
    
                    left++;
                }else if(sum==target){
    
                    r.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //  duplicate removal 2： Added to... For the first time List Then we have to go to the heavy ！
                    while(left<right && nums[left]==nums[left+1]){
    
                        left++;
                    }
                    while(left<right && nums[right]==nums[right-1]){
    
                        right--;
                    }
                    //  Keep looking for 
                    right--;
                    left++;
                }
            }
        }
        return r;
    }
}