侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【排序, 双指针】三数之和

GabrielxD
2022-04-14 / 0 评论 / 0 点赞 / 349 阅读 / 805 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
## 题目

15. 三数之和


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

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:

输入:nums = []
输出:[]

示例 3:

输入:nums = [0]
输出:[]

提示:

  • 0 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

解题

方法一:排序 + 双指针

思路

将数组排好序,遍历一个数 nums[i] 使三数之和 ($a + b + c = 0$) 转换为两数之和 ($b + c = -a$)

然后定下左指针 left 初始指向 i+1 表示第二个数,右指针 right 初始指向 nums.length-1 表示第三个数,两个指针向中间移动直至相撞时停止

计算三数之和 sum,由于数组是升序的,则有:

  • 当 $sum<0$ 时需要将 sum 增大,故将左指针右移
  • 当 $sum>0$ 时需要将 sum 减小,故右指针左移
  • 当 $sum=0$ 时 ${nums[i], nums[left], nums[right]}$ 是一组合法的解 这时将三个数字加入结果集中,左右指针继续向中间移动,这时移动的过程中若遇到连续的相同数字,为防止有效解重复,要跳过这些相同的数字

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        // 遍历以确定下来一个数
        for (int i = 0; i < len; i++) {
            // 遇到连续的相同数字则跳过
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 初始化左右指针
            int left = i + 1, right = len - 1;
            // 终止条件: 两指针相撞
            while(left < right) {
                // 计算三数之和
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    // 小了 需要增大 左指针右移
                    left++;
                } else if (sum > 0) {
                    // 大了 需要减小 右指针左移
                    right--;
                } else {
                    // 相同 得出一组合法的解
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 继续向中移动
                    left++;
                    right--;
                    // 遇到连续的相同数字跳过
                    while(left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }

        return ans;
    }
}
剪枝优化
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        if (len < 3 || nums[0] > 0 || nums[len - 1] < 0) {
            // 剪枝: 数组长度不够或者数组里元素都大于或都小于0不存在解
            return ans;
        }

        // 剪枝: 第一个数字如果大于0 其与右边两个数字加和的结果不可能是0了
        for (int i = 0; i < len && nums[i] <= 0; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1, right = len - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }

        return ans;
    }
}
0

评论区