15. 三数之和

知乎ID: 码蹄疾
码蹄疾，毕业于哈尔滨工业大学。
小米广告第三代广告引擎的设计者、开发者；
负责小米应用商店、日历、开屏广告业务线研发；
主导小米广告引擎多个模块重构；
关注推荐、搜索、广告领域相关知识;

题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

分析

排序，然后把三个数求和的解就转化为两个数相加等于某个数。
求解两个数相加等于某个数，用双指针法即可。
关键在于处理重复的问题。重复的问题最开始想直接用java的contains方法去做，因为java中contains方法也需要遍历，时间复杂度就不能接受了，第一次提交超时了。
由于拍完序了。所以重复问题的处理只需要判断相邻两个是不是相等，如果相等移动指针即可。

Code

超时的版本

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            int l = i + 1;
            int r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    List<Integer> target = new ArrayList<Integer>();
                    target.add(nums[i]);
                    target.add(nums[l]);
                    target.add(nums[r]);
                    if (!res.contains(target)) {
                        res.add(target);
                    }
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return res;
    }
}

AC版本

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1;
            int r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return res;
    }
}

扫码关注