leetcode两数求和从初步到优化

前言

◆ ◆ ◆ ◆

上周有小伙伴去面试，小明问了一下面试的情况，顺便问问题目。他说有一道题是根据输入数组以及结果，返回两数的数组下标。这个听着就很熟悉，因为leetcode的第一题，于是就重新回顾了一下。

题目

◆ ◆ ◆ ◆

顺便找了个中文版：

方法一

◆ ◆ ◆ ◆

初步第一眼看着并不难，因为是两个for循环遍历一下，就可以找出结果，方法比较粗暴

时间复杂度：两层 for 循环，O（n²）

空间复杂度：O（1）

方法二

◆ ◆ ◆ ◆

上面的方法比较粗暴，优化空间还是有的。最大的问题就是两重for循环，首先解决的是能不能一个for循环就能搞定。

我们看一下核心代码：

换一个理解：

for(int j=(i+1);j<nums.length;j++){ sub=target-nums[i] if(nums[j]==sub){ }

第二层 for 循环的作用是是遍历所有的元素，看哪个元素等于sub，时间复杂度为 O（n）。

有没有一种方法，不用遍历就可以找到元素里有没有等于 sub 的？

我们最爱的hashMap！

我们可以把数组的每个元素的值保存为map 的 key，下标保存为 value 。

这样只需判断sub是否存在于map就行，而此时的时间复杂度仅为 O（1）。

于是就有了第二种方法：

时间复杂度：O（n）

空间复杂度：所谓的空间换时间,hashMap 的空间复杂度变为 O（n）

方法三

◆ ◆ ◆ ◆

方法二中的的第一个for仅仅起到赋值作用，而这个赋值好像是可以加到下面的for当中的。于是就有了方法三：

当然这个也有个小问题，因为如果第一个数是结果中的某一个的话，第一次的map中是找不到它的，所以这个有个小问题，欢迎大神加微信交流~miraclesComing

总结

◆ ◆ ◆ ◆

程序优化里面，空间换时间，时间换空间，都是一个比较常用的方法，牺牲小部分来换取高性能，其实还是可取的。