[数据结构与算法]【LeetCode - Java】15. 三数之和（中等）

1. 题目描述

2. 解题思路

这道题目卡了非常久，暴力算法做不出来，优化后的暴力也不到位，而且需要去除重复的三元组。起初考虑过先排序后再找对应的三元组，这样就可以避免重复的判断提高效率，但后来又感觉排序最快也就O(nlogn) 的复杂度，似乎不太行（因为我以为官解的答案会变态地优化成 O(n) 的复杂度）…结果一看官解…好家伙还真的是先排序，然后跳过一部分的重复值。

这道题目没多少自己的思路，感觉是属于那种“你见过就会做，没见过就不会”的那种题目，单纯记录一下吧。

3. 代码实现

3.1 暴力（卒 | 时间超限）

public List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        ArrayList<List<Integer>> result = new ArrayList<>();
        HashSet<Map<Integer,Integer>> maps = new HashSet<>();
        for (int i = 0; i < length - 2; i++) {
            for (int j = i + 1; j < length - 1; j++) {
                for (int k = j + 1; k < length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        HashMap<Integer, Integer> map = new HashMap<>();
                        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
                        map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
                        map.put(nums[k], map.getOrDefault(nums[k], 0) + 1);
                        if (!maps.contains(map)) {
                            maps.add(map);
                            result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        }
                    }
                }
            }
        }
        return result;
    }

3.2 改进暴力（卒 | 时间超限）

public List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        HashSet<Map<Integer, Integer>> maps = new HashSet<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Set<Integer> set = map.keySet();
        for (Integer a : set) {
            for (Integer b : set) {
                int c = -a - b;
                if (a == b) {
                    if (a == 0) {
                        if (map.get(0) >= 3)
                            add(a, b, c, maps, lists);
                    } else {
                        if (map.get(a) >= 2 && map.containsKey(c))
                            add(a, b, c, maps, lists);
                    }
                } else {
                    if (a != c && b != c){
                        if (map.containsKey(c))
                            add(a, b, c, maps, lists);
                    }else {
                        if(map.get(c)>=2)
                            add(a, b, c, maps, lists);
                    }
                }
            }
        }
        return lists;
    }

    public void add(int a, int b, int c, HashSet<Map<Integer, Integer>> maps, ArrayList<List<Integer>> lists) {
        HashMap<Integer, Integer> test = new HashMap<>();
        test.put(a, test.getOrDefault(a, 0) + 1);
        test.put(b, test.getOrDefault(b, 0) + 1);
        test.put(c, test.getOrDefault(c, 0) + 1);
        if (!maps.contains(test)) {
            maps.add(test);
            lists.add(Arrays.asList(a, b, c));
        }
    }

3.3 排序+双指针

public List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        int length = nums.length;
//        Arrays.sort(nums);
        sort(nums, 0, length - 1);
        int i = 0;
        while (i < length - 2) {
            int j = i + 1, k = length - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    lists.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (nums[j] == nums[++j] && j < k) ;
                } else if (nums[i] + nums[j] + nums[k] > 0)
                    k--;
                else
                    j++;
            }
            while (nums[i] == nums[++i] && i < length - 2) ;
        }
        return lists;
    }

    public static void sort(int[] nums, int i, int j) {
        int a = i, b = j;
        if (j > i) {
            int m = nums[i];
            while (i < j) {
                while (nums[j] >= m && i < j) {
                    j--;
                }
                if (i < j) {
                    nums[i] = nums[j];
                    i++;
                }
                while (nums[i] <= m && i < j) {
                    i++;
                }
                if (i < j) {
                    nums[j] = nums[i];
                    j--;
                }
            }
            nums[i] = m;
            sort(nums, a, i - 1);
            sort(nums, j + 1, b);
        }
    }

这是使用Arrays.sort()代替我自己写的快排的最好表现：

3.4 对比

第一种暴力法的时间复杂度是O(n3)，第二种暴力法的时间复杂度是O(n2)，而排序+双指针的时间复杂度也是O(n2)，那为什么同样是 O(n2) 的时间复杂度，第二种暴力法却时间超限呢？ 其实应该很大一部分原因是因为利用HashSet与HashMap进行结果的 重复性判断从而消耗了大量的时间，而排序+双指针则可以直接避免进行重复性判断。

在排序+双指针的解法当中，一开始我是利用自己写的快排去实现，后来想了一下可以试试用现成的Arrays.sort()，果然性能比自己写的要好一点。