Problem description:

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

  1. Sort the array
  2. Pick indices from 0…n-2. To n-2 is because we need to find 3 item sequence. If we sort the array, need to at least save one spot for right element.
  3. Bypass duplicate element
  4. Use two pointers, one goes from i+1 toward right, the other one goes from n toward left
  5. If the sum of two pointers can not make the sequence zero, move the point.
    To clarify, we can only move one pointer to make the result close to zero.

Example:
input nums[-1, 0, 1, 2, -1, -4]
sort nums[-4, -1, -1, 0, 1, 2]

start from nums[0]= -4, pointer1= nums[1], pointer2= nums[6-1]

Solution:
Time: O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l +=1 
                elif s > 0:
                    r -= 1
                else:
                    res.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1; r -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() <= 2) return res; //edge case check
        
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size()-2; ++i){ //-2 is because last possible 3Sum sequence could be last 3 item, 
                                                //and the center is n-2
            
            if(i>0 && nums[i] == nums[i-1]) //pass duplicate elements
                continue;
            
            int j=i+1, k=nums.size()-1;
            int target = 0-nums[i]; //because the other two elements would make sequence zero
            
            while(j< k){
                if(nums[j]+ nums[k] == target){
                    res.push_back(vector<int>{nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                    while(j<k && nums[j]==nums[j-1]) j++;//skip same element
                    while(j<k && nums[k]==nums[k+1]) k--;//skip same element
                }
                else if(nums[j]+ nums[k]>target){
                    k--;
                }
                else{
                    j++;
                }
            }
        }
        
        return res;

    }
};

second time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        /*
        1. sort array
        2. totally three pointers, one pointer as a start point, other two traverse
        3. two traverse pointer, left and right, decrease or increase beased on different conditions
        */
        if(nums.size()< 3) return vector<vector<int>>();
        
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for(int i= 0; i< nums.size()-2; i++){
            if(i> 0 && nums[i] == nums[i-1]) continue;
            int left= i+1, right= nums.size()-1;
            while(left< right){
                int result= nums[i]+ nums[left]+ nums[right];
                if(result == 0) {
                    res.push_back(vector<int>{nums[i], nums[left++], nums[right--]});
                    while(left< right && nums[left]== nums[left-1]) left++;
                    while(left< right && nums[right]== nums[right+1]) right--;
                }
                else if(result < 0) left++;
                else right--;
            }
        }
        return res;
    }
};