3.给你一个包含n个整数的数组nums, 判断nums中是否存在三个元素a,b,c,使得a+b+c=0?请你找出所有满足条件且不重复的三元组。
时间: 2024-05-13 17:12:46 浏览: 164
这个问题可以使用双指针的方法来解决。首先将数组排序,然后枚举第一个数a,再在剩余的数中使用双指针来寻找满足条件的b和c。
具体来说,我们可以先将数组从小到大排序,然后从左到右枚举第一个数a。对于每个a,我们使用两个指针i和j分别指向a的右侧和最右侧,然后在i和j之间寻找满足条件的b和c。
具体的查找过程如下:
1. 当i=j时,退出循环
2. 如果a+nums[i]+nums[j]<0,则说明nums[i]太小,需要将i右移一位
3. 如果a+nums[i]+nums[j]>0,则说明nums[j]太大,需要将j左移一位
4. 如果a+nums[i]+nums[j]=0,则说明找到了一组解,将这个解保存下来,并将i右移一位,j左移一位
需要注意的是,在查找b和c的时候需要去重。如果当前的a和上一次枚举的a相同,则可以直接跳过当前的枚举。
以下是代码示例:
```
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 先排序
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // 去重
int j = n - 1;
for (int k = i+1; k < j; k++) {
if (k > i+1 && nums[k] == nums[k-1]) continue; // 去重
while (k < j-1 && nums[i] + nums[k] + nums[j-1] >= 0) j--; // 将j移到最后一个满足条件的位置上
if (nums[i] + nums[k] + nums[j] == 0) {
res.push_back({nums[i], nums[k], nums[j]});
}
}
}
return res;
}
```
阅读全文