Leetcode 15. 3Sum (https://www.InterviewRecipes.com/3sum) (https://youtu.be/MmhfOzYMYPk)
/* 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