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

三斤和他的喵的个人博客 / 518 / 3 / 创建于 4年前 / 更新于 4年前

前言

工作一段时间之后，最大的感觉就是算法好像没什么用，确实不会算法也能胜任平常的工作，但是总觉得缺了点什么，所以最近抽空复习了以前刷的 Leetcode，希望在这里找到一群志同道合的人。

两数之和（Two Sum）

这是 LeetCode 的第一题，总体来说是比较简单的，题干如下：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
示例:
    给定 nums = [2, 7, 11, 15]，target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
来源：力扣

简单来说就是给定一个数组，让你找到和为 target 的两个元素的索引。

解题思路

主要有 两种解题思路 ：

暴力解法：两层循环，外部循环的当前值与target的差值为内层循环需要定位的值。时间复杂度O(n^2)，空间复杂度O(1)。
优雅解法：一层循环，引入map，循环的当前值与target的差值在map中查找，如果不存在则将当前值作为键放入map，值的索引作为map的值，存在就返回。时间复杂度O(n)，空间复杂度O(n)。相比于暴力解法其实就是空间换时间。

代码实现

暴力解法GO实现：

/*暴力解法
思路：
    两层循环，外部循环的当前值与target的差值为内层循环需要定位的值
*/
func twoSumForce(nums []int, target int) (result []int) {
    length := len(nums)
    if length <= 0 {
        return
    }
    for i := 0; i < length; i++ {
        for j := i + 1; j < length; j++ {
            // 找到了就直接返回
            if nums[j] + nums[i] == target {
                return []int{i,j}
            }
        }
    }
    return
}

优雅解法GO实现：

/*优雅解法
思路：
    一层循环，引入map，循环的当前值与target的差值在map中查找，如果不存在则将当前值作为键放入map，值的索引作为map的值。
*/
func twoSumElegant(nums []int, target int) (result []int) {
    if len(nums) <= 0 {
        return
    }
    var m = make(map[int]int)
    for index, value := range nums {
        if v, ok := m[target-value]; !ok {
            // 将当前值和索引放入map中
            m[value] = index
        } else {
            return []int{index,v}
        }
    }
    return
}

总结

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

算法 leetcode two sum 学习

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

三斤

三斤和他的喵

课程读者 172 声望

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

《L04 微信小程序从零到发布》

从小程序个人账户申请开始，带你一步步进行开发一个微信小程序，直到提交微信控制台上线发布。

《G01 Go 实战入门》

从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。

推荐文章：

更多推荐...

ELK学习总结 23 / 3 |

[求职] 陈大剩的个人简历 15 / 22 |

📙《高并发的哲学原理》开源图书发布十一天 star 数已经破千！ 47 / 16 |

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 23 / 3 |

PHP实现汉诺塔算法 21 / 9 |

PHP使用动态规划实现最优红包组合 33 / 5 |

讨论数量: 3

captain2021

Laravel 5.8 译者 420 声望 / 开发 @ 谈笑风生

function twoSum($nums, $target) {
    $count = count($nums);
    if ($count <= 0) {
        return '';
    }

    $tmp = [];  // 中间交换数组
    for ($i = 0; $i < $count; $i++) {
        // 如果当前值不等于目标值减第一个key的值，则将 $tmp 数组的内容置换为当前值和key
        if ($nums[$i] != $target - array_key_first($tmp)) {
            $tmp = [];
            $tmp[$nums[$i]] = $i;
        } else {
            // 如果匹配，根据 $tmp 当前键的值返回所属 key 和 当前 $i
            return [$tmp[array_key_first($tmp)], $i];
        }
    }

    return [];
}

echo twoSum([1,7,8,5,6], 18); // output: []
echo twoSum([1,7,8,5,6], 15); // output: [1,2]

搞了个 php 的实现

4年前评论

三斤和他的喵（楼主）

厉害啦， :+1:

幽弥狂

用 PHP 的函数速度怕不是最快的。。你这个时间复杂度有点高吧

captain2021 （作者）

@幽弥狂说的也是，我想想有什么办法替换不，大佬有什么指教不

幽弥狂

课程读者 165 声望 / PHP 开发 @ 小赢科技

function twoSum($nums, $target) {
        $data = [];
        foreach($nums as $key => $val) {
            $data[$val] = $key;
        }

        foreach($nums as $k => $v) {
            $dataKey = $target-$v;
            if (isset($data[$dataKey]) && $k != $data[$dataKey]) {
                return [$k, $data[$dataKey]];
            }
        }

        return [];
    }

LeetCode 上最推荐的方式吧

file

3年前评论

皮皮强

70 声望

laravel社区发Go不合适吧

3年前评论

三斤和他的喵（楼主）

有帮助就点个赞没帮助就过一下，那么纠结干嘛😷

皮皮强（作者）

@三斤和他的喵考虑到社区到管理啦，会让大家找东西更方便

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

帮助

未填写

私信

文章归档

7 篇 2020 年 5 月 19 篇 2020 年 4 月 5 篇 2020 年 3 月

3年前让我们一起啃算法----最后一个单词的长度 3年前让我们一起啃算法----删除排序链表中的重复元素 II 3年前让我们一起啃算法----删除排序链表中的重复元素 3年前让我们一起啃算法----爬楼梯 3年前让我们一起啃算法----三数之和

8 让我们一起啃算法----两数之和 8 职场软技能，这些就够了！（三） 6 职场软技能，这些就够了！（二） 5 让我们一起啃算法----无重复字符的最长子串 4 让我们一起啃算法---- 实现 strStr

博客标签

最长不重复子串

双指针思路

成为赞助商