面试算法7：数组中和为0的3个数字

题目

输入一个数组，如何找出数组中所有和为0的3个数字的三元组？需要注意的是，返回值中不得包含重复的三元组。例如，在数组[-1，0，1，2，-1，-4]中有两个三元组的和为0，它们分别是[-1，0，1]和[-1，-1，2]。

分析

这个题目是面试题6的加强版。如果输入的数组是排序的，就可以先固定一个数字i，然后在排序数组中查找和为-i的两个数字。我们已经有了用O（n）时间在排序数组中找出和为给定值的两个数字的方法，由于需要固定数组中的每个数字，因此查找三元组的时间复杂度是O（n2）。

解

public class Test {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result = threeSum(nums);
        for (List<Integer> res : result) {
            System.out.println(res);
        }
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if (nums.length >= 3) {
            Arrays.sort(nums);

            int i = 0;
            while (i < nums.length - 2) {
                twoSum(nums, i, result);

                // 在移动指针的时候需要跳过所有相同的值，以便过滤掉重复的三元组
                int temp = nums[i];
                while (i < nums.length && nums[i] == temp) {
                    ++i;
                }
            }
        }
        return result;
    }

    private static void twoSum(int[] nums, int i, List<List<Integer>> result) {
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] == 0) {
                result.add(Arrays.asList(nums[i], nums[j], nums[k]));

                // 在移动指针的时候需要跳过所有相同的值，以便过滤掉重复的三元组
                int temp = nums[j];
                while (nums[j] == temp && j < k) {
                    ++j;
                }
            }
            else if (nums[i] + nums[j] + nums[k] < 0) {
                ++j;
            }
            else {
                --k;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50