LEETCODE 15. 3Sum 解题思路分析

题目大意:

三数之和

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

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

示例:

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

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=15

解题思路分析:

本题是2sum的升级版,但是解题思路却完全不一样。要想找到3个数的和为0,我们需要先确定一个数字,然后再找到另外两个数之和与第一个数字是相反数,这虽然是一句废话,但是却能得到一个结论,即满足条件的三个数字,要么全是0,要么必定有正有负,全是正数或者全是负数是无法满足和为0的。因此,我们首先可以给数组按照大小升序排列,排列后,从数组第一个数字开始循环,设当前数字为n1,接下来我们需要找后两个数字,这时需要第二层循环,本层循环需要使用到双指针,左指针指向n1右侧第一个数字n2,右指针指向数组最后的数字n3,这样三个数字已经集齐,我们查看n1+n2+n3的和sum,如果sum大于0,此时向左移动右指针,使得n3变小。同理,如果sum小于0,向右移动左指针使n2变大。如果sum等于0,当前的n1,n2,n3即是一个合理解。找到合理解后,同时向右移动左指针,向左移动右指针。

另外第一层循环时可以做一个剪枝处理,当前数字如果大于0时,说明另外2个数字也都大于0,之后不会再出现合理解,可直接返回。

最后,本题还需要考虑去除重复结果,在第一层循环以及第二层循环移动2个指针时,如果当前数字等于之前数字,可以跳过。

实现代码:

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums); // 排序数组
    // 返回结果
    List<List<Integer>> res = new ArrayList<>();
    // 循环数组,确定第一个数字
    for(int i=0;i<nums.length;i++){
        // 当前数字
        int n = nums[i];
        // 如果等于前一个数字,跳过
        if(i>0&&n==nums[i-1]) continue;
        // 当n大于0时,不会再找到合理解,结束循环
        if(n>0) break;
        // 定义左右两个指针,找到能组成合理解的另外两个数
        int left=i+1,right=nums.length-1;
        // 当左指针小于右指针
        while(left<right){
            // 左指针数字
            int l=nums[left];
            // 右指针数字
            int r=nums[right];
            // 三个数字之和
            int sum=n+l+r;
            // 和等于0时为合理解
            if(sum==0){
                // 将三个数字加入返回结果
                res.add(Arrays.asList(n,l,r));
                // 向右移动左指针,找到一个不等于当前左指针数字的下一个数
                while(left<right&&nums[left]==l) left++;
                // 向左移动右指针,找到一个不等于当前右指针数字的下一个数
                while(left<right&&nums[right]==r) right--;
            }else if(sum<0){ // 和小于0
                left++; // 向右移动左指针,增加左指针数字
            }else{ // 和大于0
                right--; // 向左移动右指针,减小右指针数字
            }
        }
    }
    return res;
}

本题解法执行时间为26ms。

Runtime: 26 ms, faster than 97.02% of Java online submissions for 3Sum.

Memory Usage: 55.9 MB, less than 5.29% of Java online submissions for 3Sum.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-15-3sum-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

LEETCODE 15. 3Sum 解题思路分析》有3条回应

  1. Pingback引用通告: LEETCODE 16. 3Sum Closest 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

  2. Pingback引用通告: LEETCODE 454. 4Sum II 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

  3. Pingback引用通告: LEETCODE 18. 4Sum 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。