原题
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
解法
思想
三指针,先对数组进行排序,既有助于组合去重,也可以将问题简化。第一个指针确定后,剩下的问题变成leetcode167-两数之和II-输入有序数组的问题。
代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums==null|| nums.length<3){
return result;
}
Arrays.sort(nums);
//第一个指针的移动范围
for(int i=0;i<nums.length-2;i++){
if(nums[i]>0) return result;
// 对已经出现过的数字直接跳过 不再进行处理
if(i!=0 && nums[i] == nums[i-1]) continue;
int second = i+1; // 从当前位置开始
int third = nums.length-1; // 从尾部开始
while(second<third){
int sum = -(nums[second] + nums[third]);
if(sum == nums[i]){ // 找到该数组
result.add(Arrays.asList(nums[i],nums[second],nums[third]));
//跳过相同的元素
while(second<third && nums[second] == nums[second+1]) second++;
while(second<third && nums[third] == nums[third-1]) third--;
}
if(sum <= nums[i]) third--;
else second++;
}
}
return result;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode15-%e4%b8%89%e6%95%b0%e4%b9%8b%e5%92%8c/