力扣 || 15.三数之和--Golang

131 阅读 0 评论 87 点赞

我是靠谱客的博主无私黑米，这篇文章主要介绍力扣 || 15.三数之和--Golang，现在分享给大家，希望可以做个参考。

知识点：数组
难度：中等

题目：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例：

复制代码

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

**方法：**三指针法（在实现中解释）
Golang实现：

复制代码

func threeSum(nums []int) [][]int {
    //1、先排序
    sort.Ints(nums)
    //构造输出三元组的集合
    result := [][]int{}

//2、三指针法：三个指针指向三个数a,b,c
    //将a+b+c=0转化为b+c=-a
    //从排好序的最左边的数开始，
    //令其等于a，然后依次循环，令a等于其他数
    //在每一轮循环中，把a看成定值，寻找b,c,使得b+c=-a
    //这时在每一轮之内，相当于求解两数之和问题
    for i := 0; i < len(nums)-1; i++ {
        
        //如果最小的数a都大于0，则不存在这样的三元组
        //退出循环
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        
        //在每一轮中
        //使b等于大于a的最小的数，c等于大于a的最大的数
        j := i + 1
        z := len(nums) - 1
        for z > j {
            b := nums[j]
            c := nums[z]
            //判断a+b+c的值，若大于0.则大数c往左移动
            if nums[i]+b+c > 0 {
                z--
            //判断a+b+c的值，若小于0.则小数b往右移动
            } else if nums[i]+b+c < 0 {
                j++
            } else {
                //如果a+b+c既不大于0，也不小于0，即为等于0
                //这里即找到了满足条件的三元组
                item := []int{nums[i], b, c}
                result = append(result, item)
                //跳过重复数据
                for j < z && nums[j] == nums[j+1] {
                    j++
                }
                for j < z && nums[z] == nums[z-1] {
                    z--
                }

j++
                z--
            }
        }
    }
    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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func threeSum(nums []int) [][]int {
    //1、先排序
    sort.Ints(nums)
    //构造输出三元组的集合
    result := [][]int{}

    //2、三指针法：三个指针指向三个数a,b,c
    //将a+b+c=0转化为b+c=-a
    //从排好序的最左边的数开始，
    //令其等于a，然后依次循环，令a等于其他数
    //在每一轮循环中，把a看成定值，寻找b,c,使得b+c=-a
    //这时在每一轮之内，相当于求解两数之和问题
    for i := 0; i < len(nums)-1; i++ {
        
        //如果最小的数a都大于0，则不存在这样的三元组
        //退出循环
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        
        //在每一轮中
        //使b等于大于a的最小的数，c等于大于a的最大的数
        j := i + 1
        z := len(nums) - 1
        for z > j {
            b := nums[j]
            c := nums[z]
            //判断a+b+c的值，若大于0.则大数c往左移动
            if nums[i]+b+c > 0 {
                z--
            //判断a+b+c的值，若小于0.则小数b往右移动
            } else if nums[i]+b+c < 0 {
                j++
            } else {
                //如果a+b+c既不大于0，也不小于0，即为等于0
                //这里即找到了满足条件的三元组
                item := []int{nums[i], b, c}
                result = append(result, item)
                //跳过重复数据
                for j < z && nums[j] == nums[j+1] {
                    j++
                }
                for j < z && nums[z] == nums[z-1] {
                    z--
                }

                j++
                z--
            }
        }
    }
    return result
}