15. 3Sum
1. Description
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.
2. Example
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
3. Constraints
- 0 <= nums.length <= 3000
- $-10^5$ <= nums[i] <= $10^5$
4. Solutions
Two Pointers
n = nums.size()
Time complexity: O($n^2$)
Space complexity: O(n)
class Solution {
public:
vector<vector<int>> threeSum(const vector<int> &nums) {
auto sorted_nums(nums);
sort(sorted_nums.begin(), sorted_nums.end());
vector<vector<int>> indexes;
for (int i = 0; i < sorted_nums.size() && sorted_nums[i] <= 0; ++i) {
if (i > 0 && sorted_nums[i] == sorted_nums[i - 1]) {
continue;
}
for (int j = i + 1, k = sorted_nums.size() - 1; j < k;) {
if (sorted_nums[i] + sorted_nums[j] + sorted_nums[k] < 0) {
++j;
} else if (sorted_nums[i] + sorted_nums[j] + sorted_nums[k] == 0) {
vector<int> solution{sorted_nums[i], sorted_nums[j], sorted_nums[k]};
indexes.emplace_back(solution);
++j;
while (j < k && sorted_nums[j] == sorted_nums[j - 1]) {
++j;
}
} else {
--k;
}
}
}
return indexes;
}
};