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-解题思路分析/