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.
Answer
The time complexity of brute force solution is O(n3), which is definitely time exceeded. So consider the solution of 2 sum first.
First sort the given array, then using 2 pointers to control the sum of three numbers. Move right the left pointer when the sum is less than 0 and move left the right pointer when the sum is bigger than 0.
The total time complexity is O(n2).
Code
C++
vector<vector<int>> res = vector<vector<int>>();
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, k = nums.size() - 1;
while(j < k)
{
if(nums[i] + nums[j] + nums[k] < 0|| (j > i + 1 && nums[j] == nums[j + 1]))
j++;
else if(nums[i] + nums[j] + nums[k] < 0 || (k < nums.size() - 1 && nums[k] == nums[k - 1]))
k--;
else
{
vector<int> temp = {nums[i], nums[j], nums[k]};
res.push_back(temp);
j++;
k--;
}
}
}
return res;
