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:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

Submission 1 – Brute-force

The brute-force solution is O(N^3) and it will exceed the time limit. This is a failed attempt, I will try to optimize the submission tomorrow.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                for(int k = j + 1; k < nums.length; k++) {
                    if(i == j || i == k || j == k) continue;
                    if(nums[i] + nums[j] + nums[k] == 0 &&
                       nums[i] <= nums[j] && nums[j] <= nums[k]) {
                        List<Integer> t = List.of(nums[i], nums[j], nums[k]);
                        if(!res.contains(t)) {
                            res.add(t);
                        }
                }      
                }
            }
        }
        return res;
    }
}

Submission 2

It again fails.

class Solution:
    def twoSum(self, s, nums) -> List[List[int]]:
        res = []
        for i in nums:
            if nums[i] > 0:
                nums[i] -= 1
                if (s - i) in nums and nums[s - i] > 0:
                    res.append([i, s-i])
                nums[i] += 1
        return res
        
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        d = dict()
        for n in nums:
            if n in d:
                d[n] += 1
            else:
                d[n] = 1
        
        for i in d:
            d[i] -= 1
            two = self.twoSum(-i, d)
            
            if two and len(two):
                for t in two:
                    t.append(i)
                    t.sort()
                    if t not in res:
                        res.append(t)
                        
            d[i] += 1
        
        return res

Submission 3

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        nums.sort()
        
        for i in range(len(nums) - 2):
            if nums[i] > 0:
                break
            l = i + 1
            r = len(nums) - 1
            
            while(l < r):
                s = nums[i] + nums[l] + nums[r]
                if s == 0 and [nums[i], nums[l], nums[r]] not in res:
                    res.append([nums[i], nums[l], nums[r]])
                elif s < 0:
                    l += 1
                else:
                    r -= 1
                    
        return res

Submission 4 & Solution

My problem in the previous submissions is that I used the ‘in’ function, it should be slow on a list and exceeds the time limit.

Instead, since the array is sorted, we should only take the first number in a series of the same number. Comparison after putting the 3 numbers together can be expensive.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        nums.sort()
        length = len(nums)
        for i in range(length - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l = i + 1
            r = length - 1
            
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s == 0:
                    res.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l+1] == nums[l]:
                        l += 1
                    while l < r and nums[r-1] == nums[r]:
                        r -= 1
                    l += 1
                    r -= 1
                elif s < 0:
                    l += 1
                else:
                    r -= 1
                 
        return res

200708 Revisited(C++ Version)

Description

Submission

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for(int i = 0; i < nums.size(); ++i) {
            for(int j = i + 1, k = nums.size() - 1; j < k; ) {
                if(nums[j] + nums[k] < -nums[i])j++;
                else if(nums[j] + nums[k] > -nums[i])k--;
                else if(nums[j] + nums[k] == -nums[i]) {
                    res.push_back({nums[i], nums[j], nums[k]});
                    while(j + 1 < nums.size() && nums[j+1] == nums[j]) j++;
                    while(j < k && nums[k-1] == nums[k])k--;
                    j++; k--;
                }
            }
            while(i + 1 < nums.size() && nums[i+1] == nums[i]) i++;
        }
        return res;
    }
};