转载

Leetcode第1题 Two Sum题解(Java)

前言

我是一个非科班出身的程序员，所以伴随着职业生涯中的很多点，我们都有对因为出身而知识匮乏的恐惧。所以，在我进入职业生涯没有多久，我就买齐了大学计算机科学的教材硬看。所以，虽然是非科班出身，算法和数据结构对我来说并不陌生。那时候，我对TCP/IP详解，对编译原理，对信息检索等大部头也有深刻的兴趣。

但是实话说，那样的学习成效一般，我基本上了解一切的算法和数据结构，这对我在写代码的时候，选择数据结构确实起了很大作用，但是具体怎么实现，我也就是浅尝辄止的看了书，没有自己进行过实践。

相对来说，因为08-09年，我们开展基于lucene的站内搜索引擎服务的业务，我有一段时间对信息检索扎的是足够深的。我曾经hack掉lucene的数据结构，在里面实现了我自己需要的一些东西，比如绕过索引步骤（相对非常慢），直接修改lucene数据机构里面的一些非文本字段，从而实现对索引特定部分的超快更新。这一hack需要对lucene的数据结构非常熟悉，对搜索引擎的原理非常熟悉，而且涉及到索引更新，缓存更新，等等一切流程。当然这种hack方法并不具有工业化意义，那时候我们对开源的理解还太浅薄。所以，这些东西，就成了偶尔自己可以用用，但是并不能成为一个长期维护项目的屠龙之术。

跑题了，说到这些话题只是说，我觉得计算机科学是标准实践科学，懂原理没用，我看了很多算法书，但是懒得做题，所以算法的编写能力就是不行。17年，我曾经尝试面试facebook，对方一个印度程序员提出的题目其实用二叉树很好解决。不过，他问了我一个中序遍历的问题，这本不是难题。但是我只是看过，没写过相关代码，当时就蒙住了。所以，这东西还是要实践。那一年其实作为准备，我只是学了一个普林斯顿的算法课，但是没咋刷LeetCode，所以，想了想，也是自己咎由自取。

现在我倒不是说非要去硅谷，日本看起来也许也是不错的选择。但是我觉得有生之年，刷穿LeetCode是有价值的，所以，决定做一遍。而这系列文章则既是副产品，也是帮我确保每个题目不管喜欢与否，都认真做一遍的暴涨。

首先声明我不是算法大师，普通老程序员一名，我也知道LeetCode刷题文很多，我没有野心做最好的，只想做一个自己的版本。大家不比横向比较，但是发现了我的错漏，欢迎指出，我会乐意改进的。

题目

难度：简单

原题：

大概意思是：

给定一个整数数组，返回两个索引号，保证对应的数字加起来等于指定目标值。

你可以假定每一个输入有且仅有一个解，但是同一个元素不能使用两次。

例如，

给定数组 nums = [2, 7, 11, 15] 目标 target = 9

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

所以返回[0,1]

解法1 暴力解法

这道题其实涉及不到什么复杂的数据结构和算法。望文生义就可以想到暴力解法。那就是双重循环，每层从0到n-1（n为数组元素数），在循环体内测试两者相加是否为目标值，是则输出并退出（因为只有一个解）。另外题目有要求同一个元素不能使用两次，那么加一个if语句判断即可。

那么代码就很好写，这是我刷题的时候的写法（我的写法一般都不够简洁，但是很好懂）。

这个代码可以运行正确，也可以提交成功，运行时间是79ms，速度只超过了6.2%的java提交解法。基本上这是一个可用，但是垃圾的解法。对你的面试用处不大。如果每个问题你只会暴力解法，多半找不到工作。

我们简单分析下，双重循环所以是n平方的复杂度O(n2)，当n很大的时候时间性能无法接受。

解法2 哈希表两遍法

暴力法最大的问题是双重循环，也就是n平方的复杂度。如果我们可以把数组里面的元素用哈希表保存，那么我们就可以一重循环解决问题。

第一遍循环，我们把数组里面的元素都用哈希表保存，key是数字，value是数字所在的索引号。

然后，第二遍循环，我们用目标减去当前数字，这样得到了可以和当前数字相加得到目标值的对应数字。然后在哈希表里面寻找这个数字，如果有这个数字，那么我们就找到了结果，返回即可。（同时你要判断，如果正好选到的这个数字就是当前循环的数字，那么就跳过）

这个方法其实是利用了哈希表寻找一个key不需要遍历的优点。哈希表可以用近乎常量的时找到指定的key，当然，哈希有碰撞问题，遇到了碰撞问题，则性能会下降。但是对于简单问题，一般语言，库内建的哈希算法就足以保证足够好了。但是使用哈希表会造成空间复杂度提高。至于哈希表数据结构本身怎么做到这一点的，我们也许以后的题目有机会详细聊聊，有机会也可以针对Java标准库的实现代码做分析。（如果大家有兴趣的话，可以留言，我可以考虑单独撰文做这个分析）

下面是我的具体解法：

这个代码可以正常运行，也可以提交，结果是运行时间4ms，超过了83.37%的java提交。

这个算法时间复杂度是2n，也就是O(n)。空间复杂度也是O(n)。

这个已经是最优解了。但是仍旧有一个更好的最优解，那就是用哈希表可以单遍循环解决问题么？我想把这个解法最最优解放在V+会员区。实际上面试用前面的最优解绝对足够了。

未来这个系列文章的思路也如此，暴力和标准解法，最优解放在免费阅读区，更优化的最优解和扩展思考放在付费区。

解法3 排序+两端逼近法

这个方法是复旦计算机学院的@以德服人怪猫提供的，他的思路在于python的哈希表可能没办法保证常数时间访问，所以先对数组排序，然后从数组的大小端逼近结果，我们取一个左指针和右指针，分别从左右端出发，然后计算和，如果和大于目标，则右指针向前一步，如果小于目标则左指针向后一步。这样，一次排序O(n log(n))+一次遍历O(n)即可计算出结果。不过因为我们最后要输出的是序号，排序则序号丢失，所以我们需构建一个二维数组把序号保存下，这样多一个O(n)，但是整体仍旧是性能不错的。

我的实现代码如下：

提交后的运行结果是49ms。

解法4 哈希表单遍法

其实，单遍法和两遍法从时间和空间复杂度上没有区别。复杂度考察的是增长，多一遍循环，跟n无关，所以并不会造成复杂度的上升。实际代码中也是如此。如果两遍代码更好理解更简洁，那么两遍也好。但是作为思考，去努力的去掉一遍循环也不是错误，是可以进行思考的。但是在现实生活中，写代码的时候，这并不是我们要强求的点。

我以前写代码喜欢追究极致的体验，曾经我做的某些代码，性能优化的特别好，也有很独特的解决方法。但是后来交给其他人维护的时候发现，他们很难看懂这些代码，完全不知道怎么维护。后来，为了整个项目的协作，我不得不把一些代码降低难度又重新实现了一遍。这样大家都看得懂，维护性就好多了，项目也更容易协同了。

单遍法的要点是边循环，边检查哈希表里面有没有对应的加起来等于目标值的数字。如果有则输出退出。如果没有退出则把自己加入到哈希表里面去。在这个问题里面有一个巧合，同一个元素不能用两次，这样的循环，每个元素检查的时候，自己都还没有进入哈希表，所以还可以比前两个方案减少一个if语句，不用判断自己和自己组合的情况。

我的解法是