专栏首页苦逼的码农【leetcode】15:三数之和

【leetcode】15:三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解答

这做这道题之前,我们先来简化一下,就是把三数之和,改成两数之和,也就是找出数组中所有满足 a + b = target 的组合。简化后的这道题该怎么做呢?我们可以这样做,先把数组进行排序,然后采用双指针的方法,从排序后的数组头尾两边向中间逼近,如果这两个数之和小于 target,则左边的指针向右移动,如果两个数之和大于 target,则右边指针向左移动,代码如下:

    public List<List<Integer>> twoSum(int[] nums) {
        if(nums == null || nums.length < 1)
            return new ArrayList<>();

        List<List<Integer>> res = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        while(i < j){
            if(nums[i] + nums[j] < target){
                i++;
            }else if(nums[i] + nums[j] > target){
                j--;
            }else{
                List<Integer> tmp = new ArrayList<>();
                tmp.add(nums[i]);
                tmp.add(nums[j]);
                res.add(tmp);
                // 过滤掉重复的
                while(i < j && nums[i] == nums[i+1])i++;
                while(i < j && nums[j] == nums[j-1])j--;
            }
        }
        return res;
    }

现在改成题目中的三数之和,即找出所有 a + b + c = 0的三元组,其实和二元组差不多,我们可以锁定一个数,然后把问题转换为两数之和,即找出 a + b = -c 的所有二元组,其中的 -c 相当于我们的 target。代码如下:

    public List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length < 1)
            return new ArrayList<>();

        List<List<Integer>> res = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        for(int k = 0; k < nums.length; k++){
            // 过滤掉重复的
            if(k > 0 && nums[k] == nums[k-1]){
                continue;
            }
            int target = 0 - nums[k];
            int i = k + 1;
            int j = nums.length - 1;
            while(i < j){
                if(nums[i] + nums[j] < target){
                 i++;
               }else if(nums[i] + nums[j] > target){
                   j--;
               }else{
                   List<Integer> tmp = new ArrayList<>();
                  tmp.add(nums[k]);
                  tmp.add(nums[i]);
                  tmp.add(nums[j]);
                  res.add(tmp);
                  // 过滤掉重复的
                  while(i < j && nums[i] == nums[i+1])i++;
                  while(i < j && nums[j] == nums[j-1])j--;
                  i++;
                  j--;
               }
            }
        }

        return res;
    }

优化一下,如果nums[k] > 0的后,那 k 以及 k 后面的数都大于 0,此时不可能会出现 a + b +c = 0 的三元组。

   public List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length < 1)
            return new ArrayList<>();

        List<List<Integer>> res = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        for(int k = 0; k < nums.length; k++){
            // 优化
            if(nums[k] > 0){
                break;
            }
            // 过滤掉重复的
            if(k > 0 && nums[k] == nums[k-1]){
                continue;
            }
            int target = 0 - nums[k];
            int i = k + 1;
            int j = nums.length - 1;
            while(i < j){
                if(nums[i] + nums[j] < target){
                 i++;
               }else if(nums[i] + nums[j] > target){
                   j--;
               }else{
                   List<Integer> tmp = new ArrayList<>();
                  tmp.add(nums[k]);
                  tmp.add(nums[i]);
                  tmp.add(nums[j]);
                  res.add(tmp);
                  // 过滤掉重复的
                  while(i < j && nums[i] == nums[i+1])i++;
                  while(i < j && nums[j] == nums[j-1])j--;
                  i++;
                  j--;
               }
            }
        }

        return res;
    }

本文分享自微信公众号 - 苦逼的码农(di201805),作者:帅地

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【算法精讲】分享一道很不错的算法题

    郑重声明:本文为苦逼的码农原创,未经同意禁止任何形式转载,特别是那些直接复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢

    帅地
  • 【leetcode】16. 最接近的三数之和

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假...

    帅地
  • TwoSum 相关问题思路总结

    TwoSum 作为 LeetCode 的第一题存在,想必大家应该对其并不陌生。如果仅仅是看这道题目本身,并不难,思想也特别的简单。

    帅地
  • 【python-leetcode448-循环排序】找到所有数组中消失的数字

    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    绝命生
  • python-快速排序

    核心思想:取一个初始值,将数组中比该值小的放在其左边,比其大的放在右边, 再对左、右子数组进行相同操作,直到数组排好序。

    绝命生
  • Leetcode Golang 75. Sort Colors.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • 【python-leetcode287-循环排序】寻找重复的数

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个...

    绝命生
  • Leetcde Golang 26. Remove Duplicates from Sorted Array.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88902453

    anakinsun
  • 数据结构算法操作试题(C++/Python)——四数之和

    数据结构算法操作试题(C++/Python):数据结构算法操作试题(C++/Python)——目录

    莫斯
  • 【python-leetcode15-双指针】三个数之和为零

    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组...

    绝命生

扫码关注云+社区

领取腾讯云代金券