题目:
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入: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] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
提示:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
解题思路:
暴力法搜索时间复杂度为 O( N 3 N^3 N3),可通过双指针动态消去无效解来优化效率。
算法流程:
-
先将 nums 排序,时间复杂度为 O( N l o g N NlogN NlogN)。
-
固定 3 个指针中最左(最小)元素的指针 k,双指针 i,j 分设在数组索引 ( k , l e n ( n u m s ) k,len(nums) k,len(nums))两端。
-
双指针 i, j 交替向中间移动,记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合:
- 当 nums[k] > 0 时直接break跳出:因为 nums[j] >= nums[i] >= nums[k] > 0,即 3 个元素都大于 0 ,在此固定指针 k 之后不可能再找到结果了。
- 当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]:因为已经将 nums[k - 1] 的所有组合加入到结果中,本次双指针搜索只会得到重复组合。
- i,j 分设在数组索引 (
k
,
l
e
n
(
n
u
m
s
)
k,len(nums)
k,len(nums)) 两端,当i < j 时循环计算s = nums[k] + nums[i] + nums[j],并按照以下规则执行双指针移动:
- 当s < 0时,i += 1并跳过所有重复的nums[i];
- 当s > 0时,j -= 1并跳过所有重复的nums[j];
- 当s == 0时,记录组合[k, i, j]至res,执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j],防止记录到重复组合。
代码:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//数组从小到大排序
Arrays.sort(nums);
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < len -2; i++){
//如果最小的数大于0则不可能三个数的和为0, 直接退出
if(nums[i] > 0){
break;
}
//如果和上一个数相同,则有重复解。
//即当a = d时,a + b + c = d + b + c = 0, 寻找下一个不同的数(简称:去重)
if(i > 0 && nums[i] == nums[i-1]){ //i > 0是因为可能i = 0时去重出现异常
continue;
}
//取另外两个数,判断三数之和是否为0
int j = i + 1, k = len - 1;
int sum;
while(j < k){
sum = nums[i] + nums[j] + nums[k];
//如果三数之和大于0,则说明最大数nums[k]太大了,k向左移,同时去重
if(sum > 0){
while(j < k && nums[k] == nums[--k]);
//如果三数之和小于0,则说明中间数nums[j]太小了,j向右移,同时去重
}else if(sum < 0){
while(j < k && nums[j] == nums[++j]);
//如果三数之和等于0, 则把三数添加到答案
}else{
res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[k])));
//nums[j]增大, nums[k]减小, 依旧可能满足三数之和为0,继续遍历去重
while(j < k && nums[k] == nums[--k]);
while(j < k && nums[j] == nums[++j]);
}
}
}
return res;
}
}
复杂度分析:
- 时间复杂度 O( N 2 N^2 N2):其中固定指针k循环复杂度 O(N),双指针 i,j 复杂度 O( N N N)。
- 空间复杂度 O( 1 1 1):指针使用常数大小的额外空间。