[leetcode] 15. Sum of three numbers

15、 Sum of three numbers

subject ：

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 1：

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

Example 2：

 Input ：nums = []
 Output ：[]

Example 3：

 Input ：nums = [0]
 Output ：[]

Tips ：

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10 ^5

Their thinking ：

Sort + Double pointer

The difficulty of this problem is how to get rid of repeated solutions .

Algorithm flow ：

1. Special judgement , For array length n, If the array is null Or the array length is less than 3, return [ ].
2. Sort the array .
3. Traversing the sorted array ：
4. if nums[i]>0nums[i]>0： Because it's sorted , So there can't be three numbers that add up to 00, Direct return .
5. For repeating elements ： skip , Avoid duplicate solutions
6. Left pointer L=i+1, Right pointer R=n-1, When L<R when , Execute loop ：
7. When nums[i]+nums[L]+nums[R]==0, Execute loop , Judge whether the left and right bounds are repeated with the next position , Remove duplicate solutions . At the same time L,R Move to the next position , Looking for new solutions
8. If sum is greater than 0, explain nums[R] Too big ,R Move left
9. If sum is less than 0, explain nums[L] Too small ,L Move right

Reference code ：

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    
  List<List<Integer>> resList = new ArrayList<>();
        //  Special condition judgment 
        if (nums.length < 3) return resList;
        else if (nums.length == 3){
    
            if (nums[0] + nums[1] + nums[2] == 0) {
    
                List<Integer> resSingle = new ArrayList<>();
                resSingle.add(nums[0]);
                resSingle.add(nums[1]);
                resSingle.add(nums[2]);
                resList.add(resSingle);
            }
            return resList;
        } else {
    
            // 1. Sort 
            Arrays.sort(nums);
            // 2. Double pointer 
            for (int j = 0; j < nums.length - 2; j++) {
    
                if (j > 0) {
    
                    if (nums[j - 1] == nums[j]) continue;
                }
                int target = - nums[j];
                int l = j + 1;
                int r = nums.length - 1;
                while (l < r) {
    
                    int sum = nums[l] + nums[r];
                    if (sum < target) l++;
                    else if (sum > target) r--;
                    else {
    
                        List<Integer> resSingle = new ArrayList<>();
                        resSingle.add(nums[j]);
                        resSingle.add(nums[l]);
                        resSingle.add(nums[r]);
                        resList.add(resSingle);
                        l++;
                        r--;
                        while (nums[l] == nums[l-1] && nums[r] == nums[r+1] && l < r) {
    
                            l++;
                            r--;
                        }
                    }
                }
            }
            return resList;
        }
    
    }
}