15.3Sum¶
Tags: Array
Medium
Links: https://leetcode.com/problems/3sum/
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.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Answer:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int target = 0;
if (nums.size() < 3)
return result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; ++i){
if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1;
int k = nums.size() - 1;
while (j < k){
if (nums[i] + nums[j] + nums[k] < target) ++j;
else if (nums[i] + nums[j] + nums[k] > target) --k;
else{
result.push_back({nums[i], nums[j], nums[k]});
++j;
--k;
}
}
}
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};
/*
Runtime: 112 ms, faster than 41.77% of C++ online submissions for 3Sum.
Memory Usage: 16.9 MB, less than 28.24% of C++ online submissions for 3Sum.
*/
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
if (nums.size() < 3) return result;
sort(nums.begin(),nums.end());
const int target = 0;
auto last=nums.end();
for (auto a=nums.begin(); a<prev(last,2); a++) {
auto b=next(a);//next 1 postion
auto c=prev(last);//prev 1 postion
if (a>nums.begin() && *a == *prev(a)) continue; //a have processed
if (*a>0) return result;
while(b<c) {
if (*a + *b + *c < target) b++;
else if (*a + *b + *c > target) c--;
else {
result.push_back({*a,*b,*c});
while (b<c && *b==*(next(b))) b++;//when break,b != next(b),but b==prev(b).
while (b<c && *c==*(prev(c))) c--;
b++;
c--;
}
}
}
return result;
}
};
/*
Runtime: 100 ms, faster than 69.55% of C++ online submissions for 3Sum.
Memory Usage: 14.7 MB, less than 91.76% of C++ online submissions for 3Sum.
*/
方法二相较于方法一少了用unique的环节,第一种方法对于中间重复的序列通过sort和erase(unique,c.end())来实现消除,但是会在sort和unique上浪费时间。方法二则通过19,20行来消除重复序列。
这里值得注意的是序列长度小于3则返回空vector,对于一个特殊的序列如[0,0,0,0,0,0,0,...]此时如果没有if (i > 0 && nums[i] == nums[i - 1])
会出现超时情况。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = nums.size();
vector<vector<int>> res;
if (n < 3) return res;
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if (nums[i] > 0) return res;
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum < 0) ++j;
else if (sum > 0) --k;
else {
res.push_back({nums[i], nums[j], nums[k]});
while (j < k && nums[j] == nums[j + 1]) ++j;
while (j < k && nums[k] == nums[k - 1]) --k;
++j; --k;
}
}
}
return res;
}
};
Runtime: 88 ms, faster than 98.71% of C++ online submissions for 3Sum.
Memory Usage: 14.1 MB, less than 100.00% of C++ online submissions for 3Sum.