Go-Leecode-三数之和（刷题记录）

84 阅读 0 评论 56 点赞

我是靠谱客的博主成就夕阳，这篇文章主要介绍Go-Leecode-三数之和（刷题记录），现在分享给大家，希望可以做个参考。

原文地址：Go-Leecode-盛最多水的容器（刷题记录）

公众号标题写错了，在这里更改一下。。。

给定包含n个整数的数组nums，需验证出数组nums中是否存在三个元素 a、b、c，使得a+b+c=0，需找出所有和为0且不重复的三元组。

提示内容如下：

0 <= nums.length <= 3000。
-105 <= nums[i] <= 105。

示例一：

复制代码

1
输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]

示例二：

复制代码

1
输入：nums = []输出：[]

示例三：

复制代码

1
输入：nums = [0]输出：[]

首先可以对nums数组进行排序，之后开始进行循环处理，在循环中需验证当前值是否大于0，如果当前值大于0，那么再往后推两个值也是大于零的，三数之和就不可能为零，此时应结束循环，之后的逻辑打字描述可能不是很准确，可以详细看下代码，案例如下：

复制代码

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
func threeSum(nums []int) [][]int {
    sort.Ints(nums) // 排序可以方便去重和指导双指针的下一步方向
    n := len(nums)
    var res [][]int
    for i, num := range nums {
        if num > 0 {
            break // 再往后三个正数和不可能为0
        }

        if i > 0 && nums[i] == nums[i-1] { // 因为双指针从i之后取，不能使用 nums[i] == nums[i+1] 向后去重
            continue
        }

        l, r := i+1, n-1
        for l < r {
            sum := num + nums[l] + nums[r]
            switch {
            case sum > 0:
                r--
            case sum < 0:
                l++
            default:
                res = append(res, []int{num, nums[l], nums[r]})
                for l < r && nums[l] == nums[l+1] {
                    l++
                }
                
                for r > l && nums[r] == nums[r-1] {
                    r--
                }
                
                l++
                r--
            }
        }
    }
    
    return res
}