In the Leetcode 3Sum problem solution in C++ programming Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Leetcode 3Sum problem solution in C++ programming
class Solution {
private:
void findThreeNums(vector<int> &nums, int index, vector<vector<int>> &results){
int low = index + 1;
int high = nums.size() - 1;
while(low < high){
int k = nums.at(index) + nums.at(low) + nums.at(high);
if(k > 0) high--;
else if(k < 0) low++;
else if(k == 0){
results.push_back({nums.at(index), nums.at(low++), nums.at(high--)});
while(low < high && nums.at(low - 1) == nums.at(low)) low++;
}
}
}
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> results;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++){
if(i == 0 || nums.at(i - 1) != nums.at(i))
findThreeNums(nums, i, results);
// once we get to a point in our array where its only positive numbers
// we break, because it's not possible to obtain 0 with only positive numbers
if(nums.at(i) >= 0) break;
}
return results;
}
};
Also read,
- Leetcode 3Sum problem solution in C
- Leetcode 3Sum problem solution in Java
- Leetcode 3Sum problem solution in Python
- Leetcode 3Sum problem solution in C#