题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
样例
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
数据范围
0 <= nums.length <= 3000
-1e5 <= nums[i] <= 1e5
(双指针+ 排序) $O(n^2)$
这题,我们不能直接暴力和回溯,这样会超时的。
我们首先排序,保证我们的数组具有单调性。
我们这时候,开始定义 指针 i,L,R。 i 是最小的数值(数组最左边) L 在i的左端 ,R在数组长度的最右端。
当num[i] > 0 的时候,就是结束循环的时候,因为当 num[i] > 0的时候,其不可能== 0.
当num[i] == num[i-1] 时,我们这里要去重 ,这里的去重不能是 nums[i] == nums[i+1]。这样去重会漏掉一些答案
当i固定后,L,R在移动的时候要考虑的情况
判断 sum的大小 (sum是三数之和)
当 sum == 0,答案加入数组,也要进行去重 ,不去的话,会重复答案。去重之后,移动两个指针 L ++ ,R --
当 sum < 0 , L ++;
当 sum > 0 ,R --;
所有情况已经列完了,接下来看代码。
C++ 代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort (nums.begin(),nums.end());// 排序 保证单调性 .
vector <vector<int>> res;
int n = nums.size();
if (n < 3) return res;// 特判 < 3
for(int i = 0;i < n;i ++){
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i-1]) continue;//去重
int L = i + 1;
int R = n - 1;
while (L < R){//退出循环的条件
int sum = nums[i] + nums[L] + nums[R];
if (sum == 0){
res.push_back(vector<int>{nums[i],nums[L],nums[R]});
while(L < R && nums[L] == nums[L+1]) L++;
while(L < R && nums[R] == nums[R-1]) R--;
L ++;
R --;
}
if (sum < 0) L ++;
if (sum > 0) R --;
}
}
return res;
},
//我们应该在什么的情况下使用双指针。排序不会 影响得到答案。
// 双指针遵循单调性
};