题目链接
https://leetcode.com/problems/3sum/
解题思路
题目要使得a + b + c = 0,且不重复,那就可以按照 a <= b <= c来满足题意,所以需要对数组从小到大排序,这样就可以先确定a,在a的右边找b和c即可,使得b + c = -a。
代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
int len = nums.size() - 1;
if (len < 2) {
return ans;
}
sort(nums.begin(), nums.end());
//数全部小于0
if (nums[len] < 0) {
return ans;
}
for (int i = 0; i < len - 1; ++i) {
//这里nums[i]就是a,a大于,则b和c肯定都大于0,也就不用再找了
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {//a和前一个数相等,也不再找
continue;
}
//最右边的两个数加起来也没-a大
if (nums[len] + nums[len - 1] < -nums[i]) {
continue;
}
int st = i + 1, ed = len, t = -nums[i];
while (st < ed) {
//nums[st]就是b,nums[ed]就是c。
int add = nums[st] + nums[ed];
if (add == t) {
ans.push_back({ nums[i], nums[st], nums[ed] });
st++;
ed--;
while (st < ed && nums[st] == nums[st - 1]) {//过滤掉重复的数
st++;
}
while (st < ed && nums[ed] == nums[ed + 1]) {//过滤掉重复的数
ed--;
}
} else if (add < t) {//b+c<-a,b往后移
st++;
} else {//b+c>-a,c往前移
ed--;
}
}
}
return ans;
}
};
网友评论