【Leetcode】15.三数之和

15. 三数之和

题目

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

注意：答案中不可以包含重复的三元组。

 

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

方法

注意题目中要求答案中不可以包含重复的三元组，所以时间复杂度为O(n^3)的暴力解法是行不通的。之前我们曾用时间复杂度O(n)和空间复杂度O(n)解决了两数之和问题。于是我们可以从头遍历数组，对于每遍历到的一个元素num，都在数组中查找是否有两数之和为-num的另外两个元素，这样这3个元素的和就为0了。

按照这种思路的时间复杂度为O(n^2),因为这个时间复杂度大于排序所需的O(nlogn)。所以我们可以先把数组进行排序，以方便后续的操作。排序有着以下两个好处：

  1. 对于两数之和的问题，我们可以不用额外的辅助空间（哈希表）。由于数组的有序性，我们可以用双指针的思路来解决。
  2. 如果nums[i] == nums[i-1]，则可以直接跳过对于i处的遍历，以避免结果中存在重复。

算法步骤：

  • 先将数组排序，之后从头到尾遍历数组，当遍历到数组nums[i]时，用L和R左右两个指针指向在nums[i]后面的数组两端。计算三个数的和sum，判断是否满足为 0，满足则添加进结果集。

  • 如果 nums[i]大于0，则它后面的数组元素必然都大于0，三数之和必然无法等于0，结束循环.

  • 如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过

  • 当 sum == 0时，nums[L] == nums[L+1]，则会导致结果重复，应该跳过，L++。

  • 当 sum == 0时，nums[R] == nums[R-1]，则会导致结果重复，应该跳过，R–。

    代码

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
public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList(); 
    if(nums == null || nums.length < 3) 
        return res; 
    Arrays.sort(nums);  
    for(int i = 0; i < nums.length; i++) {
        if(nums[i] > 0) 
            break;
        if(i > 0 && nums[i] == nums[i-1]) 
            continue;
        int L = i+1;
        int R = nums.length-1;
        while(L < R){
            int sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                res.add(Arrays.asList(nums[i],nums[L],nums[R]));
                while (L<R && nums[L] == nums[L+1])
                    L++;
                while (L<R && nums[R] == nums[R-1])
                    R--;
                L++;
                R--;
            }
            else if (sum < 0) 
                L++;
            else if (sum > 0) 
                R--;
        }
    }        
    return res;
}