目录

力扣 0015 三数之和

Backtraxe 收录于类别力扣

2022-08-03 2022-08-04 约 323 字预计阅读 1 分钟

目录

警告

本文最后更新于 2022-08-04，文中内容可能已过时。

15. 三数之和

方法一：排序+双指针+跳过重复项

 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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) break;
            // 保证第一个数不重复
            if (i > 0 && nums[i - 1] == nums[i]) continue;
            for (int j = i + 1, k = n - 1; j < k;) { // 双指针
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    ans.add(List.of(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                    // 保证第二和第三个数不重复
                    while (j < k && nums[j] == nums[j - 1] && nums[k] == nums[k + 1]) {
                        j++;
                        k--;
                    }

                } else if (sum > 0) k--;
                else j++;
            }
        }
        return ans;
    }
}

方法二：排序+双指针+哈希表去重

时间复杂度更高

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        HashSet<List<Integer>> set = new HashSet<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1, k = n - 1; j < k;) {
                int sum = nums[i] + nums[j] + nums[k];
                List<Integer> tuple = List.of(nums[i], nums[j], nums[k]);
                if (sum == 0 && !set.contains(tuple)) {
                    set.add(tuple);
                    ans.add(tuple);
                    j++;
                    k--;
                } else if (sum > 0) k--;
                else j++;
            }
        }
        return ans;
    }
}