题目描述
给你一个整数数组 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
(枚举 + 双指针) $O(n^2)$
令n为数组的长度
i,j,k 分别为从左往右的指针,在排序之后
从前往后枚举第一个指针,再使用j = i + 1,枚举j, j, k = n - 1 双指针求出答案。
如何找出答案?
为了找到 nums[i] + nums[j] + nums[k] == 0
的三个数,
可以找使得 nums[i] + nums[j] + nums[k] >= 0
的最小的k.
如果 nums[i] + nums[j] + nums[k] == 0
即找到答案;
如果 nums[i] + nums[j] + nums[k] > 0
, 由于k是使得三数和非负的最小k,即一定有nums[i] + nums[j] + nums[k - 1] < 0,此时对应的nums[i]不存在答案
启发:在升序(降序)情况下,如果要寻找某个数是否为0,可以从找下标最小的一个数,使其大于(小于)等于0,再判断其是否为0,如果为0即找到一个答案
为什么可以使用双指针
对于某个i,j,如果此时已经找到了一个满足要求的k,即 nums[i] + nums[j] + nums[k] >= 0
然后需要枚举下一个j,由于nums升序,此时也一定有 nums[i] + nums[j + 1] + nums[k] >= 0
,
因为我们要找的k是使得 nums[i] + nums[j] + nums[k] >= 0
的最小的k,所以k可以往右移动。
如何去掉重复元素
nums经过排序后,如果 nums[i] == nums[i - 1]
, 此时 nums[i] + nums[j] + nums[k] == nums[i - 1] + nums[j] + nums[k]
答案重复
所以当 nums[i] == nums[i - 1]
,这个 nums[i]
不作处理
对于 nums[j]
同理,
nums[j] == nums[j- 1]
此时 nums[i] + nums[j] + nums[k] == nums[i] + nums[j - 1] + nums[k]
答案重复
所以当 nums[j] == nums[j - 1]
,这个 nums[j]
不作处理
由于前两个数已经确定, nums[k]
不用额外处理
说人话,如果对于某个确定答案的nums[i],如果i后面的一个数nums[i + 1]和nums[i]相等
那么num[i]求出的答案也一定适用于nums[i + 1], 所以这个答案会重复,为了避免重复,这个num[i + 1]需要跳过
C++ 代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
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++){
if(j != i + 1 && nums[j] == nums[j - 1]) continue;
while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k--;
if(nums[i] + nums[j] + nums[k] == 0) res.push_back({nums[i], nums[j], nums[k]});
}
}
return res;
}
};