15. 三数之和 15. 3Sum

[Shellbye]

题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：

[
 [-1, 0, 1],
 [-1, -1, 2]
]

第一直觉

参考两数之和的思路，加上用集合的思路去重，可以得出一个超时的解法（正确与否未知）如下

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        Set<Set<Integer>> existSet = new HashSet<Set<Integer>>();
        for(int i = 0; i < nums.length; i++) {
            Integer f = nums[i];
            
            Map<Integer, Integer> twoSum = new HashMap<>();
            for(int j = i + 1; j < nums.length; j++) {
                if(twoSum.keySet().contains(nums[j])) {
                    // 找到一个组合
                    List<Integer> p = new ArrayList<Integer>();
                    p.add(nums[i]);
                    p.add(twoSum.get(nums[j]));
                    p.add(nums[j]);
                    Set<Integer> e = new HashSet<Integer>();
                    e.add(nums[i]);
                    e.add(twoSum.get(nums[j]));
                    e.add(nums[j]);
                    if (existSet.contains(e)) {
                        continue;
                    } else {
                        existSet.add(e);
                    }
                    ret.add(p);
                    
                } else {
                    // map 中的 key value 表示 （期待的，已有的）
                    twoSum.put(0 - nums[i] - nums[j], nums[j]);
                }
            }
        }
        return ret;
    }
}

不管是否正确，反正是超时了，第一直觉往往是不准的。

先排个序

第一直觉超时之后，我翻了翻评论，发现大家都先排序了一下，那么如果能排序，排序之后带来了哪些好处呢？排序之后的一个好处就是我们可以通过从两端分别取数来合成0。如果最小的数大于0或者最大的数小于0，那么就可以直接返回。经过分析，初步可以写出如下代码：

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        // 一些特殊情况，直接退出
        if (nums.length <= 2 || nums[0] > 0 || nums[nums.length - 1] < 0) {
            return res;
        }
        List<List<Integer>> r = new ArrayList<>();
        int pre = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            int low = 0;
            int high = nums.length - 1;
            if (nums[i] == pre) {
                low = i - 1;
            }
            while (low < i && high > i) {
                int v = nums[low] + nums[i] + nums[high];
                if (v == 0) {
                    List<Integer> ans = new ArrayList<>();
                    ans.add(nums[low]);
                    ans.add(nums[i]);
                    ans.add(nums[high]);
                    r.add(ans);
                    int oldHighValue = nums[high];
                    while (high > i && oldHighValue == nums[high]) {
                        high--;
                    }
                    int oldLowValue = nums[low];
                    while (low < i && oldLowValue == nums[low]) {
                        low++;
                    }
                } else if (v > 0) {
                    high--;
                } else {
                    low++;
                }
            }
            pre = nums[i];

        }
        return r;
    }

这个代码对于一些简单的例子，都是可以通过的，但是对于包含重复的数字的例子，就会出现重复的答案，如果再用一个集合去去重，那么时间上的开销就又大了很多，而且代码也会显的比较杂乱。

处理一些特殊情况

继续查阅了一些评论，我发现很多其他人的解法还是很巧妙的，完美的避免了我的上面的方法的重复问题，其实做法很简单：就是把我的以中间点作为锚点的思路，改成第一个点作为锚点。为什么这样可以呢？我们来看一个例子，比如

[-6,-5,-2, -2, -2, 2, 3, 4]

当我们走到第二个-2的时候，按照我的思路，第一个-2之前的数字(-6,-5)就不再遍历了（避免重复），但是这里很要命的一点是，它居然有三个-2，这样一来，走到第三个-2时，又会发现一个[-2,-2,4]是符合要求的，但是我们在处理第二个-2时其实已经发现过一次了！之所以发生这种情况，是因为我们让充当过一个中间值的数字又充当了第一位的值。为了避免这种情况，我们需要记录当前这个值是否在前面使用过，新的代码如下：

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
//        System.out.println(Arrays.toString(nums));
        // 一些特殊情况，直接退出
        if (nums.length <= 2 || nums[0] > 0 || nums[nums.length - 1] < 0) {
            return res;
        }
        List<List<Integer>> r = new ArrayList<>();
        int pre = nums[0];
        boolean preUsed = false;// 用于记录前一个相等的值是否使用过
        for (int i = 1; i < nums.length; i++) {
            int low = 0;
            int high = nums.length - 1;
            if (nums[i] == pre) {
                low = i - 1;
                if (preUsed)  // 如果它和前一个数字相等，而且前一个数字已经使用过，则跳过
                    continue;
            } else {
                preUsed = false;
            }
            while (low < i && high > i) {
                int v = nums[low] + nums[i] + nums[high];
                if (v == 0) {
                    List<Integer> ans = new ArrayList<>();
                    ans.add(nums[low]);
                    ans.add(nums[i]);
                    ans.add(nums[high]);
                    r.add(ans);
                    int oldHighValue = nums[high];
                    while (high > i && oldHighValue == nums[high]) {
                        high--;
                    }
                    int oldLowValue = nums[low];
                    while (low < i && oldLowValue == nums[low]) {
                        low++;
                    }
                    if (nums[i] == pre)  // 标记使用过
                        preUsed = true;
                } else if (v > 0) {
                    high--;
                } else {
                    low++;
                }
            }
            pre = nums[i];

        }
        return r;
    }

其他解法

我们上面的解法之所以需要考虑的特殊情况比较多，是因为我们选择了中间数作为锚点，而这个中间数有有可能在别的组合中扮演第一位数，所以出现了这种复杂的情况。那么我们可以换一个锚点，即以第一位数作为锚点，这样当我们发现重复时（第二个-2），就可以直接跳过，因为此时的这个重复点作为第一个点在上一个点就处理过了，再次把它作为第一个点的话，出现将都是重复的结果了。

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        if (nums.length <= 2 || nums[0] > 0 || nums[nums.length - 1] < 0) {
            return res;
        }
        List<List<Integer>> r = new ArrayList<>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int low = i + 1;
            int high = nums.length - 1;
            while (low < high) {
                int v = nums[i] + nums[low] + nums[high];
                if (v == 0) {
                    List<Integer> ans = new ArrayList<>();
                    ans.add(nums[i]);
                    ans.add(nums[low]);
                    ans.add(nums[high]);
                    r.add(ans);
                    int oldHighValue = nums[high];
                    while (high > low && oldHighValue == nums[high]) {
                        high--;
                    }
                    int oldLowValue = nums[low];
                    while (low < high && oldLowValue == nums[low]) {
                        low++;
                    }
                } else if (v > 0) {
                    high--;
                } else {
                    low++;
                }
            }
        }
        return r;
    }