28 lines
879 B
C++
28 lines
879 B
C++
class Solution {
|
|
public:
|
|
vector<vector<int>> threeSum(vector<int>& nums) {
|
|
// The main issue is to remove duplicate answers
|
|
int n = nums.size();
|
|
sort(nums.begin(), nums.end());
|
|
vector<vector<int>> ret;
|
|
int preid = -1;
|
|
for(int i = 0; i < n; i++){
|
|
if(preid != -1 && nums[i] == nums[preid]) continue;
|
|
int l = i + 1, r = n - 1;
|
|
while(l < r){
|
|
int sum = nums[i] + nums[l] + nums[r];
|
|
if(sum == 0){
|
|
ret.push_back({nums[l], nums[r], nums[i]});
|
|
int tmp = nums[l];
|
|
while(l < r && nums[l] == tmp) l++;
|
|
preid = i;
|
|
}else if(sum > 0){
|
|
r--;
|
|
}else{
|
|
l++;
|
|
}
|
|
}
|
|
}
|
|
return ret;
|
|
}
|
|
}; |