让我们一起啃算法----三数之和

三数之和（3 Sum）

题干：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
  示例：
  给定数组 nums = [-1, 0, 1, 2, -1, -4]，
  满足要求的三元组集合为：
  [
    [-1, 0, 1],
    [-1, -1, 2]
    ]
来源：力扣

思路与让我们一起啃算法—-两数之和相似，求 两数之和 时我们引入了一个偏移指针，这题需要引入三个偏移指针。

解题思路

首先我们对 nums 进行排序，接着初始化： a 指向 nums 数组的第一个元素，b 指向 nums[a] 的后一个元素，c 指向 nums 的最后一个元素。

初始化时，b 始终指向 nums[a] 的后一个元素， c 始终指向 nums 的最后一个元素。

题目要求三数之和为 0，即 nums[b] + nums[c] = 0 - nums[a]，我们将 0 - nums[a] 记为 sum。

当 nums[b] + nums[c] 大于 sum 时，c 向左移动；当 nums[b] + nums[c] 小于 sum 时，b 向右移动；当 nums[b] + nums[c] 等于 sum 时，这时候 nums[a]， nums[b]， nums[c] 为一组有效值，记录下来，b 向右移动，c 向左移动。直到 b 大于等于 c 时，移动 a 指针再重新初始化 b 和 c，重复上面的步骤，直到 a 越界。

a 越界条件： a 大于 nums 数组倒数第三个索引时即越界。因为我们有三个指针，当 a 为数组倒数第三个索引时，b为倒数第二个索引，c为倒数第一个索引。

这里有一个注意点： a，b，c 指针在移动的过程中需要与前一次指向的数组值对比，如果相等需要继续移动，直到不相等。例如 nums[b] 为 1，b 向右移动一位，即 b++，这时候发现 nums[b] 仍为 1，b 需要继续向右移动一位，直到 nums[b] 不为 1。

上面的操作是为了保证结果中没有重复的元组。
例如 nums 为 [-1 -1 0 1 2]，假设 a 为 0，即 nums[a] 为 -1，会找到一个有效元组 [-1, 0, 1]，这时候向右移动 a ，即 a 为 1，nums[a] 为 -1 与上一次值相同，a 需要继续向右移动，否则又会找到一个有效元组 [-1, 0, 1]，这就重复了。同理 b，c 也是如此。

流程图如下：

代码实现

GO语言实现

func threeSum(nums []int) [][]int {
    var result [][]int
    if len(nums) <= 2 {
        return result
    }
    // 需要排序
    sort.Ints(nums)
    a := 0
    // 有三个指针，a 是最左边的，所以 a 最大值为 nums 倒数第三个索引
    for a <= len(nums)- 3 {

        // 保证 a 在向右移动时指向的值，不与之前的值相等
        if a != 0 && nums[a] == nums[a-1]  {
            a++
            continue
        }

        // b 为 a 的后一个指针
        b := a + 1

        // c 指向 nums 最后一个元素
        c := len(nums) -1

        // sum 的值为后续 nums[b] + nums[c] 的值
        sum := 0 - nums[a]

        // b 必须小于 c
        for b < c {

            // 保证 c 在向左偏移时指向的值，不与之前的相等
            if c < len(nums) - 1 && nums[c] == nums[c + 1] {
                c--
                continue
            }

            // 保证 b 在向右偏移时指向的值，不与之前的相等
            if b > a + 1 && nums[b] == nums[b-1] {
                b++
                continue
            }

            // 比较和
            if nums[b]+nums[c] > sum {
                c--

            } else if nums[b]+nums[c] < sum {
                b++

            } else {
                result = append(result, []int{nums[a], nums[b], nums[c]})
                c--
                b++
            }

        }
        // a 向右移动
        a++
    }
    return result

}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
github.com/wx-satellite/learning-a...

算法数据结构 leetcode

本作品采用《CC 协议》，转载必须注明作者和本文链接

三斤

三斤和他的喵

课程读者 172 声望

一个PHPer的修行之路。欢迎大家关注我的公众号《三斤和他的喵》

1 人点赞

你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程，JWT 概念及使用和 API 开发相关的进阶知识。

以构建论坛项目 LaraBBS 为线索，展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。

讨论数量: 2

yzh52521

33 声望

function threeSum($nums) {
    sort($nums);
    $len = count($nums);
    $res = [];
    for ($i=0;$i<=$len-3;$i++){
        $j= $i+1;
        $k = $len-1;
        while ($j < $k){
            if($nums[$i] == ($nums[$j]+$nums[$k])*-1){
                if(!in_array([$nums[$i],$nums[$j],$nums[$k]],$res)){
                    $res[] = [$nums[$i],$nums[$j],$nums[$k]];
                }
                $j++;
                $k--;
                while ($j<$k && $nums[$j]===$nums[$j-1]){
                    $j++;
                }
                while ($j<$k && $nums[$k]===$nums[$k+1]){
                    $k--;
                }
            }else{
                if($nums[$i]+$nums[$j]+$nums[$k]<0){
                    $j++;
                    while ($j<$k && $nums[$j]===$nums[$j-1]){
                        $j++;
                    }
                }else{
                    $k--;
                    while ($j<$k && $nums[$k]===$nums[$k+1]){
                        $k--;
                    }
                }
            }

        }

    }
    return $res;
    }

4年前评论

三斤和他的喵（楼主）

:+1:优秀

取名字好烦。

0 声望

优秀！

4年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

让我们一起啃算法----三数之和

三数之和（3 Sum）

解题思路

代码实现

GO语言实现

总结

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

让我们一起啃算法----三数之和

三数之和（3 Sum）

解题思路

代码实现

GO语言实现

总结

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录