LeetCode-15.三数之和 - sheep44044的小站

双指针#

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

1
输入：nums = [-1,0,1,2,-1,-4]
2
输出：[[-1,-1,2],[-1,0,1]]
3
解释：
4
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
5
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
6
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
7
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
8
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
输入：nums = [0,1,1]
2
输出：[]
3
解释：唯一可能的三元组和不为 0 。

示例 3：

1
输入：nums = [0,0,0]
2
输出：[[0,0,0]]
3
解释：唯一可能的三元组和为 0 。

1.代码随想录的哈希

没做出来捏☹️，这个题目用哈希真的是很麻烦和恶心，对于新手来说去重真的不简单，不只是先固定a再加上二数之和这么简单。速度也很慢479ms… 之后学到双指针再看看

1
func threeSum(nums []int) [][]int {
2
    res := make([][]int, 0)
3
    sort.Ints(nums)
4
    for i := 0; i < len(nums); i++ {
5
        if nums[i] > 0 {
6
            break
7
        }
8
        if i > 0 && nums[i] == nums[i-1] {
9
            continue
10
        }
11
        set := make(map[int]struct{})
12
        for j := i + 1; j < len(nums); j++ {
13
            if j > i + 2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2] {
14
                continue
15
            }
16
            c := -nums[i] - nums[j]
17
            if _, ok := set[c]; ok {
18
                res = append(res, []int{nums[i], nums[j], c})
19
                delete(set, c)
20
            } else {
21
                set[nums[j]] = struct{}{}
22
            }
23
        }
24
    }
25
    return res
26
}

2.双指针

思路：排序 + 固定基准数 i + 双指针寻找另外两个数

因为最大的难点就是避免重复，所以我们需要处理的是数据重复的问题。

关于处理重复这个双指针和前边的值比较，还是和后边的值比较，在我自己实践中感觉本质上一样的，但是需要注意的是：

和后边的值比较，需要注意边界问题，避免第一个和最后一个元素的越界

和前边的值比较，会停在这一堆重复数字的最后一个上面，必须强制执行一次 left++ 和 right--

1
func threeSum(nums []int) [][]int {
2
    var res [][]int
3
    n := len(nums)
4
    if n < 3 {
5
        return res
6
    }
7

8
    sort.Ints(nums)
9

10
    for i := 0; i < n-2; i++ {
11
        if nums[i] > 0 {
12
            break
13
        }
14

15
        if i > 0 && nums[i] == nums[i-1] {
16
            continue
17
        }
18

19
        left := i + 1
20
        right := n - 1
21

22
        for left < right {
23
            sum := nums[i] + nums[left] + nums[right]
24

25
            if sum == 0 {
26
                res = append(res, []int{nums[i], nums[left], nums[right]})
27

28
                for left < right && nums[left] == nums[left+1] {
29
                    left++
30
                }
31

32
                for left < right && nums[right] == nums[right-1] {
33
                    right--
34
                }
35

36
                left++
37
                right--
38
            } else if sum < 0 {
39
                left++
40
            } else {
41
                right--
42
            }
43
        }
44
    }
45

46
    return res
47
}