Problem
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: 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] ]
Solution
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { return findThreeSum(nums, 0); } vector<vector<int>> findThreeSum(vector<int>& nums, int target){ vector<vector<int>> result; if(nums.size()<3) return result; sort(nums.begin(), nums.end()); for(int i=0; i<nums.size()-2; i++){ //skip duplicate if(i!=0 && nums[i-1] == nums[i]) continue; int left = i+1; int right = nums.size()-1; while(left < right){ int remain = target - nums[i]; int sum = nums[left] + nums[right]; if(sum < remain) left++; else if(sum > remain) right--; else { vector<int> curr; curr.push_back(nums[i]); curr.push_back(nums[left]); curr.push_back(nums[right]); result.push_back(curr); left++; right--; //skip duplicate while(nums[left] == nums[left-1]) left++; while(nums[right] == nums[right+1]) right--; } } } return result; } };
Analysis
Time complexity: O(n^2) where n is the size of the array