# LeetCode: 3Sum

## 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;
int v = num[head] + num[tail];
if(v == target) {
vector<int> now(3, 0);
now[0] = num[first];
now[2] = num[tail];
ans.push_back(now);

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

}
else if(v > target)
tail--;
else