题目地址

https://leetcode-cn.com/problems/3sum/

题目描述

给你一个包含 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>> results = new ArrayList<>();
        Set<String> existsResults = new HashSet<>();

        // 枚举三个数的状态 (a, b, c)
        int length = nums.length;
        for (int a = 0; a < length; a ++) {
            for (int b = a + 1; b < length; b ++) {
                for (int c = b + 1; c < length; c ++) {
                    if (sumIsZero(nums[a], nums[b], nums[c])) {
                        List<Integer> result = Arrays.asList(nums[a], nums[b], nums[c]);
                        String uniqueKey = getUniqueKey(result);
                        if (existsResults.contains(uniqueKey)) {
                            continue;
                        }
                        results.add(result);
                        existsResults.add(uniqueKey);
                    }

                }
            }
        }
        return results;
    }

    public boolean sumIsZero(int a, int b, int c) {
        return (a + b + c) == 0;
    }

    public String getUniqueKey(List<Integer> result) {
        Collections.sort(result);
        return result.toString();
    }
}

时间复杂度 O(n^3)，n 为 nums 数组的长度。

上述代码执行超时。

hash 表查找

对于 a + b + c = 0
如果要同时枚举 a，b，c 三个数的状态，时间复杂度为 O(n^3)。可以怎么优化呢？

思考一下，如果我们枚举了 a，b 两个数的状态，是否可以推导出第三个数的状态呢？

a + b + c = 0 ==> a + b = -c ==> c = -(a + b)

通过上述等式我们可以从 a，b 两个数的状态推导出 c = -(a + b)，所以我们只需要枚举 a，b 两个数的状态，时间复杂度为 O(n^2)。
那么我们如何快速的知道是否存在 c = -(a + b) 的数呢？

查找时间复杂度 O(1) 的是什么？答案是 hash 表。

还有一个小问题，就是我们可以先排序整个数组，这样就不需要在计算 getUniqueKey 时单独排序了。

具体代码如下所示：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        Set<String> existsResults = new HashSet<>();
        Map<Integer, Integer> hash = initHash(nums);

        // 排序后 a <= b <= c
        Arrays.sort(nums);

        // 枚举两个数的状态 (a, b)
        int length = nums.length;
        for (int a = 0; a < length; a ++) {
            // 去掉 nums[a] 在 hash 表的数据
            hash.compute(nums[a], (k, v) -> v - 1);

            for (int b = a + 1; b < length; b ++) {
                int c = -(nums[a] + nums[b]);

                // c 如果小于 b，说明当前等式已经枚举过了
                if (c < nums[b]) break;

                // 去掉 nums[b] 在 hash 表的数据
                hash.compute(nums[b], (k, v) -> v - 1);
                
                if (hash.get(c) != null && hash.get(c) > 0) {
                    List<Integer> result = Arrays.asList(nums[a], nums[b], c);
                    String uniqueKey = result.toString();
                    if (!existsResults.contains(uniqueKey)) {
                        results.add(result);
                        existsResults.add(uniqueKey);
                    }
                    
                }
                
                // 增加 nums[b] 在 hash 表的数据
                hash.compute(nums[b], (k, v) -> v + 1);
            }
            // 增加 nums[a] 在 hash 表的数据
            hash.compute(nums[a], (k, v) -> v + 1);
        }
        return results;
    }

    public Map<Integer, Integer> initHash(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();

        for (int i = 0; i < nums.length; ++ i) {
            int key = nums[i];
            if (hash.containsKey(key)) {
                hash.put(key, hash.get(key) + 1);
            } else {
                hash.put(key, 1);
            }
        }

        return hash;
    }
}

时间复杂度 O(n^2)，n 为 nums 数组的长度。

耗时有点长，但是通过了，说明时间复杂度是符合题意的，但是常量系数有点大。

还能怎么优化呢？

上面的单个状态计算逻辑中，使用了 map 作为 hash 表，使用了 set 作为结果去重的判断依据。

考虑等式 a + b + c = 0。
我们在上面做的优化是如下三步：

• (1) 排序后 a <= b <= c，（去重时就不需要额外排序了）
• (2) 转换等式为 c = -(a + b)
• (3) 通过 hash 查找是否存在 c。

双指针

如果不通过 hash 表，我们还能怎么处理呢？
可以通过如下步骤：

• (1) 排序后 a <= b <= c
• (2) 转化等式为 a = -(b + c)

枚举所有的 a 需要 O(n) 的时间复杂度，我们怎么在 O(n) 的时间复杂度中同时确定所有符合条件的 b + c 呢？

因为 b <= c。
假设 b1 > b0，当 b0 + c0 == b1 + c1 时，会得到 c1 < c0 的结论。

因此，我们可以从左往右枚举 b，从有往左枚举 c 的状态。
这样，在 O(n) 的时间复杂度中就可以确定所有符合条件的 b+c。

完整代码如下所示：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();

        // 排序后 a <= b <= c
        Arrays.sort(nums);

        int length = nums.length;
        for (int a = 0; a < length; a ++) {
            // 因为 a <= b <= c
            // 如果 a > 0，等式 a + b + c == 0 就不可能成立
            if (nums[a] > 0) break;

            int b = a + 1;
            int c = length - 1;
            while (b < c) {
                int negativeA = nums[b] + nums[c];
                if (negativeA == -nums[a]) {
                    List<Integer> result = Arrays.asList(nums[a], nums[b], nums[c]);
                    results.add(result);

                    // 同时移动 b 和 c 的指针
                    b++;
                    c--;
                    
                    // 如果 b 和 b-1 的值一样，则需要向右移动 b 的指针
                    while (b < c && nums[b] == nums[b - 1]) {
                        b++;
                    }

                    // 如果 c 和 c+1 的值一样，则需要向左移动 c 的指针
                    while (b < c && nums[c] == nums[c + 1]) {
                        c--;
                    }
                } else if (negativeA > -nums[a]) {
                    // 因为 a <= 0，所以 -a >= 0
                    // 如果 b + c > -a，说明 b+c 的值太大了
                    // 要减少 b+c 的值，就需要向左移动 c 的指针
                    c--;
                } else {
                    // 因为 a <= 0，所以 -a >= 0
                    // 如果 b + c < -a，说明 b+c 的值太小了
                    // 要增大 b+c 的值，就需要向右移动 b 的指针
                    b++;
                }
            }

            // 如果 a 和 a+1 的值一样，则需要向右移动 a 的指针
            while (a+1 < length && nums[a] == nums[a + 1]) {
                a++;
            }
        }
        return results;
    }
}

上述代码多了一些去重的逻辑，如：

// 如果 b 和 b-1 的值一样，则需要向右移动 b 的指针
while (b < c && nums[b] == nums[b - 1]) {
    b++;
}

// 如果 c 和 c+1 的值一样，则需要向左移动 c 的指针
while (b < c && nums[c] == nums[c + 1]) {
    c--;
}

和

// 如果 a 和 a+1 的值一样，则需要向右移动 a 的指针
while (a+1 < length && nums[a] == nums[a + 1]) {
    a++;
}

缩减了常量系数后，耗时大大减少。