题目描述
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
样例
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
算法1
1、排序
2、for循环枚举i之后,利用双指针枚举j、k(双指针的前提是排序)
左指针起始位置为i+1,右指针起始位置为nums.size()-1
如果 当前和 < 0-nums[i] ,则将左指针向右移动
如果 当前和 > 0-nums[i] ,则将右指针向左移动
如果 当前和 = 0-nums[i] ,则将结果放入res,同时移动左右指针
结束条件:左右指针相遇
3、如何达到去重?
如果当前遍历到的nums[i]和nums[i-1]相同,则忽略
j中:还会存在第二个元素相同的情况,第三个元素相同的情况…等等
k中:还会存在第二个元素相同的情况,第三个元素相同的情况…等等
因此采用while判断,而不是if
时间复杂度
时间复杂度:O(n^2),双指针将双重循环(暴力为双重循环)优化为一维,双指针也只能做到将二维变一维,不能做到三维变一维
空间复杂度:O(1)
C++ 代码
class Solution {
public:
/*
-4 -1 -1 0 1 2
1、排序
2、for循环枚举i之后,利用双指针枚举j、k(双指针的前提是排序)
左指针起始位置为i+1,右指针起始位置为nums.size()-1
如果 当前和 < 0-nums[i] ,则将左指针向右移动
如果 当前和 > 0-nums[i] ,则将右指针向左移动
如果 当前和 = 0-nums[i] ,则将结果放入res,同时移动左右指针
结束条件:左右指针相遇
3、如何达到去重?
如果当前遍历到的nums[i]和nums[i-1]相同,则忽略
j中:还会存在第二个元素相同的情况,第三个元素相同的情况...等等
k中:还会存在第二个元素相同的情况,第三个元素相同的情况...等等
因此采用while判断,而不是if
时间复杂度:O(n^2),双指针将双重循环(暴力为双重循环)优化为一维,双指针也只能做到将二维变一维,不能做到三维变一维
空间复杂度:O(1)
根据题意:该题的nums不可能为空,则不需要特判
*/
vector<vector<int>> threeSum(vector<int>& nums) {
// 根据题意:该题的nums不可能为空,则不需要特判
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int nLeft=0,nRight=0,nSum=0;
for(int i=0;i<nums.size();i++)
{
// 去重
if(i&&nums[i]==nums[i-1]) continue;
// -4 -1 -1 0 1 2
nLeft=i+1;
nRight=nums.size()-1;
nSum=0-nums[i];
while(nLeft<nRight)
{
if(nums[nLeft]+nums[nRight]>nSum) --nRight;
else if(nums[nLeft]+nums[nRight]<nSum) ++nLeft;
else
{
res.push_back({nums[i],nums[nLeft],nums[nRight]});
++nLeft;
--nRight;
}
while(nLeft!=i+1&&nums[nLeft]==nums[nLeft-1]&&nLeft<nums.size()-1) ++nLeft;
while(nRight<=nums.size()-2&&nums[nRight]==nums[nRight+1]&&nRight>0) --nRight;
}
}
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla