给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
时间: 2023-12-23 14:02:45 浏览: 74
这是一个经典的三数之和问题。可以使用双指针的方法来解决。
具体的步骤如下:
1. 首先对数组进行排序,以便后续操作。
2. 遍历数组,对当前元素nums[i],使用双指针方法在剩余部分找到和为0的两个数。
- 定义两个指针,left指向i+1,right指向数组末尾。
- 在left < right的条件下,不断移动指针,判断nums[i] + nums[left] + nums[right]与0的关系。
- 如果等于0,将三个数加入结果集,并将left和right都向内移动一位。
- 如果小于0,说明和太小了,需要增大,将left向右移动一位。
- 如果大于0,说明和太大了,需要减小,将right向左移动一位。
- 注意要避免重复的情况,即如果移动指针后的数与移动前相等,则继续移动指针。
3. 返回结果集。
下面是相应的C++代码实现:
```cpp
#include <vector>
#include <algorithm>
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
int n = nums.size();
if (n < 3) {
return result;
}
std::sort(nums.begin(), nums.end()); // 对数组进行排序
for (int i = 0; i < n - 2; i++) {
if (nums[i] > 0) {
break; // 当前元素大于0,无法满足和为0,直接退出循环
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // 避免重复的情况
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
// 避免重复的情况
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
```
这样,调用`threeSum`函数,并传入一个整数数组`nums`,即可得到所有和为0且不重复的三元组。
阅读全文