[LeetCode 015] 3 Sum

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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

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

Note: The solution set must not contain duplicate triplets.

Difficulty
Medium

Similar Problems
[LeetCode 1] Two Sum E [LeetCode 16] 3Sum Closest M [LeetCode 18] 4Sum M [LeetCode 259] 3Sum Smaller M

Analysis

Condition:

Elements in a triplet (a, b, c) must be in non-descending order. (ie, a ≤ b ≤ c)
Only elements need to be returned, indexes need not be cared.

Idea

Since we need to find 3 elements, it's unvoidable to recursively loop the array, this causes time complexity up to O(n^2). We can sort the array first, fix an element, then use 2-sum algorithm to process the remaining elementes of the array. The premis of using two indexers way is that the array must be sorted.

e.g.
Fix nums[i], then loop nums[i+1] ~ nums[n-1]

Time: O(n^2 + nlog(n)) = O(n^2)
Space: O(n)

Solutions

1. Cpp solution

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums){
        int n = nums.size();
        vector<vector<int>> triples;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; ++i) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;  // skip duplicates
            twoSum(nums, i + 1, 0 - nums[i], triples);
        }
        return triples;
    }

    // sorted array
    void twoSum(vector<int> &nums, int start, int target, vector<vector<int>> &res){
        int i = start, j = (int)nums.size() - 1;
        while(i < j){
            int sum = nums[i] + nums[j];
            if(sum == target) {
                res.push_back({nums[start - 1], nums[i], nums[j]});
                ++i;
                --j;
                while(nums[i] == nums[i - 1]) ++i;  // skip duplicates
                while(nums[j] == nums[j + 1]) --j;  // skip duplicates
            }
            else if(sum < target) ++i;
            else --j;
        }
    }

    // hash map
    // void twoSum(vector<int> &nums, int start, int target, vector<vector<int>> &res){
    //     unordered_map<int, int> hash;
    //     for(int i = start + 1; i < nums.size(); ++i) {
    //         int val = target - nums[i];
    //         if(hash.find(val) != hash.end()) {
    //             res.push_back({nums[start], nums[i], val});
    //         }
    //         hash[val] = i;
    //     }
    // }
};

1. Cpp Solution 53 ms

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

        sort(nums.begin(), nums.end());
        vector<vector<int>> triples;
        for(int i = 0; i < n; ){
            int start = i + 1, end = n - 1;
            while(start < end){
                int sum = nums[i] + nums[start] + nums[end];
                if(sum == 0){
                    triples.push_back({nums[i], nums[start], nums[end]});
                    start++;
                    end--;
                    while(start < end && nums[start] == nums[start - 1])
                        start++;
                    while(start < end && nums[end] == nums[end + 1])
                        end--;
                }
                else if(sum < 0){
                    ++start;
                    while(start < end && nums[start] == nums[start - 1])
                        ++start;
                }
                else if(sum > 0){
                    --end;
                    while(start < end && nums[end] == nums[end + 1])
                        --end;
                }
            }
            ++i;
            while(i < n && nums[i] == nums[i - 1])
                ++i;

        }
        return triples;
    }
};

1. Cpp Solution 57

vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> triples;
    sort(nums.begin(), nums.end());
    int i = 0, last = n - 1;
    while (i < last) {
        int a = nums[i], j = i+1, k = last;
        while (j < k) {
            int b = nums[j], c = nums[k], sum = a+b+c;
            if (sum == 0) triples.push_back({a, b, c});
            if (sum <= 0) while (nums[j] == b && j < k) j++; // skip duplicate
            if (sum >= 0) while (nums[k] == c && j < k) k--; // skip duplicate
        }
        while (nums[i] == a && i < last) i++; // skip duplicate
    }
    return triples;
}

1. Golang Solution

func threeSum(nums []int) [][]int {
    all := [][]int{}
    sort.Ints(nums)
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        twoSum_(nums, &all, i+1, 0-nums[i])
    }
    return all
}

func twoSum_(nums []int, all *[][]int, idx, target int) {
    begin, end := idx, len(nums)-1
    for begin < end {
        sum := nums[begin] + nums[end]
        if sum < target {
            begin++
        } else if sum > target {
            end--
        } else {
            res := make([]int, 3)
            res[0], res[1], res[2] = nums[idx-1], nums[begin], nums[end]
            *all = append(*all, res)
            begin++
            end--
            for nums[begin] == nums[begin-1] && begin < end {
                begin++
            }
            for nums[end] == nums[end+1] && begin < end {
                end--
            }
        }
    }
}