python leetcode 之两数之和(two sum)

Leetcode，这个大名鼎鼎的刷题神器，对于将要入行码农行业或已是码农的猿猿们来说，是必不可少的的练习工具。但可能还有很多小猿们还不知道它。从今天起，我将写一个【Leetcode的刷题练Python】的系列，和大家一起用Python来解Leetcode的上面的算法题目。

Leetcode是什么？

它是一个美国的在线编程网站。官方网址是：http://leetcode.com/，打开浏览器输入网址，就可以在线写代码、提交、查看算法的优略以及个人别实现算法的对比等等。开箱即用，非常方便。

上面收录的算法题目，大多来自大公司的笔试面试题，分为简单、中等、困难三个等级，从基础到高级都有。是学习算法、练习编程、准备笔试面试的必备良器。不要迟疑，马上和我开始刷题之旅吧！

如何使用Leetcode？

Leetcode既然是美国的，自然网站语言也是英文的。但它出了正文版，且用了独立域名： https://leetcode-cn.com/ 。中文的题目描述可能更方便我们理解，英文版同时也练练我们的专业英语。具体选用什么语言各选所好，题目的编号都是对应的，也方便大家中文对照着看。我写这个系列就选中文吧。

简单注册登录，或用github等第三方账户登录，就可以看到下面的界面：

题目分“算法”，“数据库”和“shell”脚本三种，其中算法已经有840个题目，足够你过刷题的瘾了。

点击题名就进入刷题页面：

如果你看不懂中文，可以“切换为英文”；

如果你没有思路，可以看看“评论”，或者看看“题解”；

如果你想用C++、Python、Java都实现一遍，可以选择不同编程语言；

读懂了左边的题目，就可以在右边的编辑框写代码了；

写完代码，先“执行代码”看看有没有错；

如果没有错误，就可以“提交”了，提交完就能看到是否全部测试都通过，已经用时、耗费的空间、超过了百分之几的其他人等信息，这是对你算法实现的评价，不满意就再修改算法再次提交。

基本的使用就是这些。接下来正式刷题。

题目：两数之和

1. 题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

2. 解题思路和Python知识点

这个题目主要考察我们如何遍历数组（Python的列表），从中找出想要的元素。

最原始的方法就是，从头到尾，对每个元素找它后面的每一个元素是否与它匹配（也就是两者的和为target）。用两个嵌套的循环来实现，思路很正常，但是效率最低：

时间复杂度是O(n2)，空间复杂度是O(1)

好处是基本不消耗内存。

不妨实现一下这个方法，看看能跑出怎样的结果：

果不其然，提交后得到这样的令人鄙视的结果：

拿这样的算法去面试是找不到工作的！

进一步，我们想到算法无非是“以时间换空间，以空间换时间”。马儿要想跑得快，就得吃得多。每次我们遍历到某一元素时，它前面的若是已经记录下来，可能就不需要多一个嵌套的循环了。那么，问题就变成如何记录下来，让它比一个嵌套的循环速度快（耗时少）？

想想Python的数据结构中，列表、tuple和字典，那个查找速度快呢？显然是字典（据说，字典的查找速度平均是O(1)，最坏情况是O(n)）。好，那么就用字典来保存已经遍历的元素，再查找target与当前元素的差是否在字典中即可，那么它的实现就是：

这结果比上个快了100多倍，但似乎也不能让人十分满意：

看这个结果，也就是说有三分之一的Python3提交比这个速度快。Python如何实现更高效的算法呢？留给大家作为讨论话题，大家有什么思路留言讨论吧。

我的公众号：猿人学 Python 上会分享更多心得体会，敬请关注。

***版权申明:若没有特殊说明，文章皆是猿人学 yuanrenxue.con 原创，没有猿人学授权，请勿以任何形式转载。***