Leetcode第1题 Two Sum题解(Java)

前言

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

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

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

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

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

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

原题地址:https://leetcode.com/problems/two-sum/

难度:简单

原题:

给定一个整数数组,返回两个索引号,保证对应的数字加起来等于指定目标值。你可以假定每一个输入有且仅有一个解,但是同一个元素不能使用两次。
例如,

给定数组 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语句,不用判断自己和自己组合的情况。

我的解法是

这个代码可正常提交,时间为3ms,超过99.75%的java提交。

大家可以看到从运行时间来看比解决方案2没有快太多。如果这样的改进带来的结果是,代码难以读懂,或者修改逻辑的时候发现难以修改,那么则这种性能提升是毫无价值的。

本文对应的代码在我的Github可以找到 https://github.com/tinyfool/leetcode/tree/master/src/p0001

本题属于哈希表类题目,想了解更多关于哈希表的题目,可以参看哈希表专题

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据