LeetCode，三数之和

微客鸟窝

发布于 2021-08-18 15:45:17

4810

文章被收录于专栏：Go语言指北Go语言指北

力扣题目：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

解题

看到题目是否有点似曾相识(如果您看过我之前的文章的话)，没错，我们之前解过「两数之和」题，两数之和的主要解题思路：

使用哈希法，将给定的切片 nums 的索引和值，翻转存入到 map 中：
判断目标值 target - nums 中一个元素是否存在 map 中；
如果存在则找到需要的值并返回；
若不存在 map 中，则将遍历中的索引及元素值翻转存入到 map 中。

想了解详情可以看一下原文：传送门点这里。

解题「三数之和」，比较直观的解法就是使用三重循环，分别找出第一、二、三个元素，再判断和是否为零：

func threeSum(nums []int) [][]int {
    s := [][]int{}
    sort.Ints(nums)
    length := len(nums)

    for first :=0; first < length-1; first++ {
        for second :=1; second < length-1; second++ {
            for third :=2; third < length-1; third++ {
                if nums[first] + nums[second] + nums[third] == 0 {
                    s = append(s,[]int{nums[first],nums[second],nums[third]})
                } 
            }
        }
    }
    return s
}

执行结果：

输入
[-1,0,1,2,-1,-4]
输出
[[-1,0,1],[-1,2,-1],[-1,-1,2],[0,1,-1],[0,-1,1],[1,0,-1],[2,-1,-1],[-1,0,1],[-1,2,-1],[-1,-1,2]]
预期结果
[[-1,-1,2],[-1,0,1]]

发现有许多重复的答案，根据题目要求：答案中不可以包含重复的三元组，我们对代码进行改进。

改进

排序 + 双指针

为了保证不重复，我们所枚举的三元组 (a,b,c) 需要满足 a ≤ b ≤ c，保证了只有(a,b,c) 这个顺序会被枚举到，而(b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。

同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复，这时候我们只需要「跳到」下一个不相同的元素即可。

对于三元组，a + b + c = 0，在遍历的时候，我们先确定第一个元素 a ,遍历第二层循环，b 每往后枚举一个元素，由于我们将数组排序过，b 每增大时，仍要满足 a + b + c = 0的条件，那么 c 就需要相应的减小。

也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。如此，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针。

func threeSum(nums []int) [][]int {
    s := [][]int{}
    sort.Ints(nums)
    length := len(nums)
 
    // 枚举 a
    for first := 0; first < length; first++ {
        //每次枚举第一个元素，a 需要和上次使用的元素不同，避免重复
        if first > 0 && nums[first] == nums[first - 1] {
            continue
        }
        third := length -1 // c 对应的指针初始指向数组的最右端
        target := -1 * nums[first]
        //枚举b
        for second := first + 1; second < length; second++ {
            // b 需要和上一次枚举的数不相同，避免重复
            if second > first + 1 && nums[second] == nums[second - 1] {
                continue
            }
            // 需要保证 b 的指针在 c 的指针的左侧
            for second < third  && nums[second] + nums[third] > target {
                third--
            }
            // 如果指针重合，随着 b 后续的增加
            // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
            if second == third {
                break
            }
            if nums[second] + nums[third] == target {
                s = append(s, []int{nums[first], nums[second], nums[third]})
            }
        }
    }
    return s
}

❝上面解题方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法。 ❞

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-11，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自微客鸟窝微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度