3Sum

Description

🔗 Leetcode-15. 3Sum:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

Thoughts

• There cannot be duplicates between elements in a triplet, and there cannot be duplicates between triplet groups.
• The addition of three elements = 0 can be simplified to the sum of two numbers equal to the third number, so it is excellent to verify as soon as possible whether the sum of the first two numbers is in the third number (O(1) time complexity), so consider using hashing for caching. (The solution is not feasible because it is difficult to solve the problem of non-duplication between triple groups.)

Solution

Sort & Dual-Pointer (Copy)

It is now known that the problem can be solved through a brute force triple loop, but how to optimize the time complexity of the problem from O(N³) to O(N²)?

The outer loop must be unchanged, that is, for the element of the current index, how to find the other two elements in the array through one traversal so that the sum of the two elements is equal to the opposite of this element? **

So you can sort the array first (key), and then use double pointers in the inner loop to synchronize the process. The double pointers have one end at the beginning and the other at the end. The sum of the two pointer elements is compared with the inverse of the outer loop element. Therefore, it can be determined whether the left pointer moves to the right (the sum of the three numbers is less than 0) or the right pointer moves to the left (the sum of the three numbers is greater than 0). The two pointers gradually tend to the target value, and the matching points can be found through one traversal. two other elements

At the same time, pay attention to the details. There should be no duplication between triple groups, so it is necessary to exclude the situation where the current element of the inner and outer loops is the same as the previous position.

**So the brute-force solution with a time complexity of O(N³) can be optimized into an algorithm with a time complexity of O(N²) and a space complexity of O(logN) (binary recursion takes up space during sorting) **

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {
          	// Focus on the outer loop to avoid repeated problems
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1;
            int r = nums.length - 1;
            while(l < r) {
                // To avoid repeated questions, just judge the left/right situation.
                if(l != i + 1 && nums[l] == nums[l-1]) {
                    l++;
                    continue;
                }
                if(nums[l] + nums[r] + nums[i] == 0) {
                    List<Integer> cur = new ArrayList<>();
                    cur.add(nums[i]);
                    cur.add(nums[l]);
                    cur.add(nums[r]);
                    res.add(cur);
                  	// Don't forget to increment the left or right pointer
                    l++;
                }else if(nums[l] + nums[r] + nums[i] > 0) {
                    r--;
                }else{
                    l++;
                }
            }
        }
        return res;
    }
}