15. 三数之和
大约 2 分钟
15. 三数之和
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解题思路
固定 3 个指针中最左(最小)数字的指针 k,双指针 i,j 分设在数组索引 k 两端,通过双指针交替向中间移动,记录对于每个固定指针 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, 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);
List<List<Integer>> res = new ArrayList<>();
for(int k = 0; k < nums.length - 2; k++){
if(nums[k] > 0) break;
if(k > 0 && nums[k] == nums[k - 1]) continue;
int i = k + 1, j = nums.length - 1;
while(i < j){
int sum = nums[k] + nums[i] + nums[j];
if(sum < 0){
while(i < j && nums[i] == nums[++i]);
} else if (sum > 0) {
while(i < j && nums[j] == nums[--j]);
} else {
res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
while(i < j && nums[i] == nums[++i]);
while(i < j && nums[j] == nums[--j]);
}
}
}
return res;
}
}
作者:jyd 链接:https://leetcode.cn/problems/3sum/solution/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/ 来源:力扣(LeetCode)
Loading...