LeetCode: 3Sum

LeetCode: 3Sum 1

Last Updated on

Question

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]
]

Explanation

For time optimization, we need to sort the given array. Then enumerate the elements from index 0(assume value v0), try to find the 2 elements which some sum of them is -v0.

Time complexity is:

\(O(N^2) \)

Code

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > ans;
        sort(num.begin(), num.end());

        if(num.size() < 3) return ans;
        for(int first = 0; first < num.size(); first++) {
            int target = -num[first];
            int head = first + 1;
            int tail = num.size() - 1;
            while(head < tail) {
                int v = num[head] + num[tail];
                if(v == target) {
                    vector<int> now(3, 0);
                    now[0] = num[first];
                    now[1] = num[head];
                    now[2] = num[tail];
                    ans.push_back(now);
                    head++, tail--;

                    //skip same elements
                    while(head < tail && num[head] == num[head-1])
                        head++;
                    while(tail > head && num[tail] == num[tail+1])
                        tail--;

                }
                else if(v > target)
                    tail--;
                else
                    head++;
            }
            while(first < num.size()-1 && num[first+1] == num[first])
                first++;
        }
        return ans;
    }
};