三数之和
作者:
Jiarui.X
,
2023-09-19 15:18:51
,
所有人可见
,
阅读 32
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& a) {
vector<vector<int>> ans;
int n = a.size();
sort(a.begin(), a.end());
for (int i = 0; i < n - 2; i ++) {
int x = a[i];
if(i && x == a[i - 1]) continue;
if(x + a[i + 1] + a[i + 2] > 0) break;
if(x + a[n - 1] + a[n - 2] < 0) continue;
int j = i + 1, k = n - 1;
while(j < k) {
int sum = x + a[j] + a[k];
if(sum > 0) -- k;
else if(sum < 0) ++ j;
else {
ans.push_back({x, a[j], a[k]});
++ j;
while(j < k && a[j] == a[j - 1]) ++ j;
-- k;
while(k > j && a[k] == a[k + 1]) -- k;
}
}
}
return ans;
}
};