Simple solution using 3 pointers (no hashing)

• The stated problem is quite straight forward - find triplets in the array who's sum is 0.
This can be reduced to the following subproblems:

Given an index i, find pairs of indices j,k such that i != j != k such that nums[j] + nums[k] = -nums[i].
Given two pairs (a, b) and (c, d) with sum -nums[i] , ensure that a != c and a != d and b != c and b != d

Solution will be empty if nums.size() < 3.

``````vector<vector<int>> threeSum(vector<int>& nums) {
// create an empty solution set
vector<vector<int>> soln;
// base case where nums.size() < 3
if(nums.size() < 3) return soln;
// sort the array
sort(nums.begin(), nums.end());
// consider a triplet which includes element at index i
for(int i = 0; i < nums.size() - 2; i++){
/* If the element at index i is the same as the previous element, we can skip
this element, since all triplets considering nums[i] as first element are
*/
if(i > 0 && nums[i-1] == nums[i]) continue;
/*
consider a pair of indices (i+1, n-1) where n = nums.size()
*/
int j = i+1, k = nums.size() -1;
// we need to find a pair with sum = -nums[i]
int sum = -nums[i];

while(j < k){
// sum of the current pair
int s = nums[j] + nums[k];
// if the sum is less than the required sum, we increment j
if(s < sum) {
// j is incremented in a loop to ensure that duplicate values are not considered
while(nums[j] == nums[j+1] && j < k) j++;
j++; continue;
}else if(s > sum){
// k is decremented in a loop to ensure that duplicate values are not considered
while(nums[k] == nums[k-1] && k > j) k--;
k--; continue;
}
//cout << i <<' '<<j <<' '<<k<<endl;
vector<int> v;
v.push_back(nums[i]);
v.push_back(nums[j]);
v.push_back(nums[k]);
soln.push_back(v);
// increment j in a loop
while(nums[j] == nums[j+1] && j < k) j++;
// decrement k in a loop
while(nums[k] == nums[k-1] && k > j) k--;
j++; k--;
}
}
return soln;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.