LeetCode【15】三数之和

题目：

解析：
参考：https://zhuanlan.zhihu.com/p/111715985

代码：

public static List<List<Integer>> threeSum(int[] nums) {

   // 先排序
    Arrays.sort(nums);

    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {   //注意这里优化，少算两个数，因为是三数之和
        int left = i + 1;
        int right = nums.length - 1;

        if (i > 0 && nums[i] == nums[i - 1]) {   // 注意，这里容易产生重复计算 -1、-1、0、1，结果里将产生两遍 -1、0、1，题目中明确不可以包含重复的三元组
            continue;
        }

        while (left < right) {
            if (nums[left] + nums[right] == (0 - nums[i])) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 这里优化，减少重复计算
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                // 还有可能凑成0，如 -4,-2,2,4
                left++;
                right--;
            } else if (nums[left] + nums[right] > (0 - nums[i])) {
                right--;
            } else {
                left++;
            }
        }
    }

    return result;
}
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