Hash - 15. Sum of three numbers

1 Title Description

15. 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 .

2 Title Example

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 ：[]

3 Topic tips

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

4 Ideas

The time complexity of violence law Q yes O(n^3). You can fix a value first , Then, when looking for the last two values, you can use the double pointer method , Optimize the total time complexity to O(n²).
In the process of realization , Pay attention to optimization and weight removal .

First, we sort the original array , In this way, duplicate values can be gathered , Easy to remove heavy .

When determining the first element , If it's already better than 0 big , Then you can jump out of the loop , Because the following numbers are bigger than it . Such as [1,2,3,4], i = 0, nums[i]> 0, This is impossible to produce a legal situation , direct break.
When determining the first element , If you find that it is the same as the value in front of it , Then skip this round . Such as [-1,-1,0,1], After the first round , Have chosen {-1,0,1}, Now? i=1, nums[i] == nums[ i - 1], To avoid repetition , direct continue.
Next, use the double pointer ,left Point to i+1, right Point to nums.length -1. Judge one by one , And pay attention to weight removal .

Complexity analysis
· Time complexity :o(N2), among N It's an array nums The length of .

· Spatial complexity :O(log N). We ignore the space to store answers , The space complexity of the extra sort is O(log N). However, we changed the input array nums, In reality, it is not — Prescriptive permission , So it can also be seen as using an extra array to store nums Copy and sort , The space complexity is O(N).

5 My answer

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    //  Total time complexity ：O(n^2)
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;
 
        Arrays.sort(nums); // O(nlogn)
 
        for (int i = 0; i < nums.length - 2; i++) {
     // O(n^2)
            if (nums[i] > 0) break; //  The first number is greater than  0, The latter numbers are bigger than it , Definitely not 
            if (i > 0 && nums[i] == nums[i - 1]) continue; //  Remove duplicates 
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
    
                if (nums[left] + nums[right] == target) {
    
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    
                    //  Now it's time to add  left, Reduce  right, But you can't repeat it , such as : [-2, -1, -1, -1, 3, 3, 3], i = -2, left = 1, right = 6, [-2, -1, 3]  After adding your answer , Need to eliminate duplicate  -1  and  3
                    left++; right--; //  First, in any case, add and subtract 
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < target) {
    
                    left++;
                } else {
      // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }
}

Another way of writing

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        //  enumeration  a
        for (int first = 0; first < n; ++first) {
    
            //  It needs to be different from the last enumeration 
            if (first > 0 && nums[first] == nums[first - 1]) {
    
                continue;
            }
            // c  The corresponding pointer initially points to the rightmost end of the array 
            int third = n - 1;
            int target = -nums[first];
            //  enumeration  b
            for (int second = first + 1; second < n; ++second) {
    
                //  It needs to be different from the last enumeration 
                if (second > first + 1 && nums[second] == nums[second - 1]) {
    
                    continue;
                }
                //  Need assurance  b  The pointer is in  c  On the left side of the pointer 
                while (second < third && nums[second] + nums[third] > target) {
    
                    --third;
                }
                //  If the pointers coincide , With  b  Subsequent additions 
                //  There will be no satisfaction  a+b+c=0  also  b<c  Of  c  了 , You can exit the loop 
                if (second == third) {
    
                    break;
                }
                if (nums[second] + nums[third] == target) {
    
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}