Two Sum 問題的核心思想

• 2019 年 10 月 11 日
• 筆記

作者 | labuladong

來源 | labuladong

Two Sum 系列問題在 LeetCode 上有好幾道，這篇文章就挑出有代表性的兩道，介紹一下這種問題怎麼解決。

TwoSum I

這個問題的最基本形式是這樣：給你一個數組和一個整數target，可以保證數組中存在兩個數的和為target，請你返回這兩個數的索引。

比如輸入nums = [3,1,3,6],target = 6，算法應該返回數組[0,2]，因為 3 + 3 = 6。

這個問題如何解決呢？首先最簡單粗暴的辦法當然是窮舉了：

這個解法非常直接，時間複雜度 O(N^2)，空間複雜度 O(1)。

更好一點的解法，可以通過一個哈希表減少時間複雜度：

這樣，由於哈希表的查詢時間為 O(1)，算法的時間複雜度降低到 O(N)，但是需要 O(N) 的空間複雜度來存儲哈希表。不過綜合來看，是要比暴力解法高效的。

我覺得 Two Sum 系列問題就是想教我們如何使用哈希表處理問題。我們接着往後看。

TwoSum II

稍微修改一下上面的問題，要求我們設計一個類，擁有兩個 API：

class TwoSum {      // 向數據結構中添加一個數 number      public void add(int number);      // 尋找當前數據結構中是否存在兩個數的和為 value      public boolean find(int value);  }  

如何實現這兩個 API 呢，我們可以仿照上一道題目，使用一個哈希表輔助find方法：

進行find的時候有兩種情況，舉個例子：

情況一：如果連續 add 了 [3,2,3,5]，那麼freq是{3:2,2:1,5:1}，執行find(6)，由於 3 出現了兩次，3 + 3 = 6，所以返回 true。

情況二：freq是{3:2,2:1,5:1}，執行find(7)，那麼key為 2，other為 5 時算法可以返回 true。

除了上述兩種情況外，find只能返回 false 了。

對於這個解法的時間複雜度呢，add方法是 O(1)，find方法是 O(N)，空間複雜度為 O(N)，和上一道題目比較類似。

但是對於 API 的設計，是需要考慮現實情況的。比如說，我們設計的這個類，使用find方法非常頻繁，那麼每次都要 O(N) 的時間，豈不是很浪費費時間嗎？對於這種情況，我們是否可以做些優化呢？

是的，對於頻繁使用find方法的場景，我們可以進行優化。我們可以參考上一道題目的暴力解法，藉助哈希集合來針對性優化find方法：

這樣sum中就儲存了所有加入數字可能組成的和，每次find只要花費 O(1) 的時間在集合中判斷一下是否存在就行了，顯然非常適合頻繁使用find的場景。

三、總結

對於 TwoSum 問題，一個難點就是給的數組無序。對於一個無序的數組，我們似乎什麼技巧也沒有，只能暴力窮舉所有可能。

一般情況下，我們會首先把數組排序再考慮雙指針技巧。TwoSum 啟發我們，HashMap 或者 HashSet 也可以幫助我們處理無序數組相關的簡單問題。

另外，設計的核心在於權衡，利用不同的數據結構，可以得到一些針對性的加強。

最後，如果 TwoSum I 中給的數組是有序的，應該如何編寫算法呢？答案很簡單，前文 雙指針技巧匯總 寫過：int[] twoSum(int[] nums, int target) {      int left = 0, right = nums.length - 1;      while (left < right) {          int sum = nums[left] + nums[right];          if (sum == target) {              return new int[]{left, right};          } else if (sum < target) {              left++; // 讓 sum 大一點          } else if (sum > target) {              right--; // 讓 sum 小一點          }      }      // 不存在這樣兩個數      return new int[]{-1, -1};  }