leetcode15-三数之和

原题

给你一个包含 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/

发表评论

电子邮件地址不会被公开。