题目描述
给你一个包含 n
个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c
,使得a + b + c = 0
?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
样例
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
算法1
(双指针) $O(n^2)$
最暴力的写法可以用三重循环,这样会超时不可取;但是根据暴力的思想我们是不是可以对其进行优化,
因此:我们先固定一个点,然后求出以改点作为第一个点的方案判断是否有解由于利用了双指针所以这里我们可以先排个序
假设剩余的两个指针为j,k那么j = i + 1 , k = nums.size() - 1;
当k指针向左移动时,j指针也会单调向右走
第二重循环确定了第二个指针——第三个指针会根据前两个指针来唯一确定方案
nums[i] + nums[j] + nums[k] >= nums[i] + nums[j] + nums[k-1],因此无论如何如果j向左走的话k如果还向
右走的话值只会越来越大,肯定不会符合题意
接下来需要注意的就是要判重
C++ 代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if(nums.empty())return {};
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size() ;i ++){
if (i && nums[i] == nums[i - 1]) continue; //判重
for(int j = i + 1 , k = nums.size() - 1;j < k; j++){
int c = -nums[i];
if(j > i + 1 && nums[j] == nums[j-1])continue; // 判重
while(j < k && nums[j] + nums[k] > c)k--;
if(j >= k) break;
if(nums[j] + nums[k] == c)res.push_back({nums[i],nums[j],nums[k]});
}
}
return res;
}
};