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

總結

◆ ◆ ◆ ◆

程式優化裡面，空間換時間，時間換空間，都是一個比較常用的方法，犧牲小部分來換取高性能，其實還是可取的。