1. 首页
  2. LeetCode

每日一道 LeetCode (52):三数之和

每日一道 LeetCode (52):三数之和

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:三数之和

难度:中等

题目来源:https://leetcode-cn.com/problems/3sum/

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

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

示例:

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

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

解题思路

之前一段时间都在写 JVM 和 Tomcat 的一系列相关的文章,刷力扣题就给空下了,今天开始接着捡起来做题。

首先这道题我第一个反应是套三个循环,肯定做得出来,时间复杂度是 O(n^3) ,放在力扣里面,按照一贯的尿性结果肯定是超时,这个方案我现在都已经懒得写了(对,我现在就是这么飘),除了锻炼下写代码的能力,对于算法好像没啥提升。

其他的方案又想不出来,没办法,只能去翻答案。

答案上的思路就很有意思了,第一件事儿就是先给数组排序,把这个数组变成一个有序数组。

三个数加起来结果要是 0 ,会有一种特殊情况就是 0 + 0 + 0 = 0

刨除掉上面这种情况,那么肯定第一位是负数,后面第二位只能比第一位大,第三位要比第二位大(这不是显而易见嘛)。

套上前面的特殊情况,那么会有一个确定的关系 a <= b <= c

这个问题解到这里,还是没有跳脱出来三重循环,那么时间复杂度依然还是 O(n^3) ,这肯定不行,还需要继续优化。

目标放在把时间复杂度降低到 O(n^2) 上,那么就是两重循环要搞定所有的事儿,最外层的循环也就是找 a 的那个循环,这个肯定是无法避免的,能玩的滑头也就只剩下第二重循环了,在找 b 和 c 的过程,想办法找到内在的联系,在一次循环中,直接把 b 和 c 全都找出来。

如果我们固定了 a 和 b ,那么只会有一个唯一的 c 来满足 a + b + c = 0 。当第二重循环往后再循环一个 b1 的时候,这时如果存在 a + b1 + c1 = 0 ,那么这个 c1 一定要比之前的 c 来的要小。

这样我们可以在第二重循环里面考虑一个双指针的方案,一个数组从小到大排列,取 b 的时候我们从小到大取,取 c 的时候我们从大到小来取,这时,我们取 b 和 c 其实是并列在第二重里面的,这样我们强行把三重循环降成了两重循环。

这里的 b 和 c 可以抽象成两个指针,左指针和右指针,左指针每像右移动一位,右指针向左有可能移动 n 位,这和数组的元素有关,最差情况下会达到移动 n 次,因此,时间复杂度也是 O(n) ,第一重循环还有一个 O(n) ,所以整体的时间复杂度会达到 O(n^2) 。

代码:

public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();
    // 最外层循环,迭代 a
    for (int a = 0; a < n; ++a) {
        // 由于元素不能重复,遇到相同的直接下次循环
        if (a > 0 && nums[a] == nums[a - 1]) {
            continue;
        }
        // c 对应的指针初始指向数组的最右端
        int c = n - 1;
        int target = -nums[a];
        // 迭代 b
        for (int b = a + 1; b < n; ++b) {
            // 一样先判断是否和上次迭代的元素是否相同
            if (b > a + 1 && nums[b] == nums[b - 1]) {
                continue;
            }
            // b 的位置在 c 的左侧
            while (b < c && nums[b] + nums[c] > target) {
                --c;
            }
            // 如果出现了指针重合,就可以退出循环了,说明没找到对应的 c
            if (b == c) {
                break;
            }
            // 如果出现了 b 和 c 加起来等于 -a ,说明我们找到的最后的结果
            if (nums[b] + nums[c] == target) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[a]);
                list.add(nums[b]);
                list.add(nums[c]);
                ans.add(list);
            }
        }
    }
    return ans;
}

不知道各位还记不记得之前两数之和的解法,当我们确定了 a 和 b 以后,最终寻找 c 的时候还可以把整个数组放在一个哈希表中,通过哈希表的特性来判断当前 c 是否存在,如果不存在,则进入下一次循环。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code