3Sum

• leetcode 15
• Medium
• Company Tags: Amazon, Microsoft, Bloomberg, Facebook, Adobe
• Tags: Two Points, Array
• Similar Problems: Two Sum, 3Sum Closest, 4Sum, 3Sum Similar

Description

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

Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

Previous Thinking

This Problem uses the different thinking compared with Two Sum. It is because the time complexity of Sort, which is O(nlog n). Use hashMap to solve the 2Sum problem, the complexity is just O(n), which doesn' t allow us to use Sort. However, When the demension of the problem becomes larger, we can use Sort now, which is jus the base of Two Points method.

Anothert interesting thing I want to mention here again is dealing with duplicates. When we met a duplicate, just skip to see the next step.

C++ Solution

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() < 3) return res;

        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size() - 2; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1;
            int k = nums.size() - 1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0){
                    res.push_back({nums[i],nums[j],nums[k]});
                    while(j < k && nums[j++] == nums[j]);
                    while(j < k && nums[k--] == nums[k]);
                }else if(sum < 0){
                    while(j < k && nums[j++] == nums[j]);
                } else{
                    while(j < k && nums[k--] == nums[k]);
                }
            }
        }

        return res;
    }
};

Java Solution

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length < 3) return res;

        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0){
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while(j < k && nums[j++] == nums[j]);
                    while(j < k && nums[k--] == nums[k]);
                }else if(sum < 0){
                    while(j < k && nums[j++] == nums[j]);
                }else{
                    while(j< k && nums[k--] == nums[k]);
                }
            }
        }
        return res;
    }
}

Summary

• A fancy template to remove dup[licates: while(j < k && nums[j++] == nums[j]);
• Arrays.asList(...) return a FixedSizeArray.