Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/* Watch video explanation here: https://youtu.be/MmhfOzYMYPk */
class Solution {
vector<vector<int>> ans; // Stores the final answer.
/* Skip the duplicates. */
int increment(vector<int>& nums, int cur) {
int n = nums.size();
int j=cur+1;
while (j < n && nums[j] == nums[cur]) {
j++;
}
return j;
}
/* Skip the duplicates. */
int decrement(vector<int>& nums, int cur) {
int j=cur-1;
while (j >= 0 && nums[j] == nums[cur]) {
j--;
}
return j;
}
/* Pairs of numbers in array `nums` from index `start` to
* index `end` with sum `target`.
*/
void twoSum(vector<int>& nums, int start,
int end, int target, int a) {
while (start < end) {
if (nums[start]+nums[end] == target) {
// Add the triple in the answer.
ans.push_back({nums[start], nums[end], a});
start = increment(nums, start);
end = decrement(nums, end);
} else if (nums[start]+nums[end] < target) {
start = increment(nums, start);
} else {
end = decrement(nums, end);
}
}
}
public:
vector<vector<int>> threeSum(vector<int>& nums) { // Time: O(n^2)
sort(nums.begin(), nums.end()); // O(nlogn)
int n = nums.size();
for (int i=0; i<n; i=increment(nums, i)) { // n *
int a = nums[i];
twoSum(nums, i+1, n-1, -a, a); // O(n)
}
return ans;
} // Space: O(1)
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.