LeetCode ：1.兩數之和解題報告及演算法優化思路

2019 年 10 月 3 日
筆記

最近開始重拾演算法，在 LeetCode上刷題。順便也記錄下解題報告以及優化思路。

題意

給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那兩個整數，並返回他們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，你不能重複利用這個數組中同樣的元素。

示例：

nums = [2, 7, 11, 15], target = 9    返回 [0, 1]

題意很簡單，就是尋找兩個數，這兩個數相加的值等於 target。且保證每組輸入一定會有答案。

解題思路

從題意上看，只需要找到那兩個數即可。那麼首先可以想到的就是枚舉組合兩個數的和，但是 組合數 的數量是非常大的，這個思路就可以作罷。

兩個數相加的和等於 target, 反過來，對於一個數 nums[i]，能否在數組裡找到另外一個數 nums[j] 使得 nums[j] = target - nums[i]。這樣我們只需要關心一個數即可。

暴力枚舉

簡單粗暴，一重循環用來枚舉 nums[i], 另一重用來尋找 nums[j]。

程式碼：

public class Solution {      public int[] TwoSum(int[] nums, int target) {          for(int i = 0; i < nums.Length; i ++) {              int res = target - nums[i];              for(int j = 0; j < nums.Length; j ++) {                  if(i == j) continue;                  if(res == nums[j]) return new int[] {i, j};              }          }          return new int[] {};      }  }

執行用時：904ms
記憶體消耗：29.6MB
用時排名：超過21.29%

29個案例，耗時近 1 秒。由於這裡僅有循環輔助變數，記憶體消耗其實不大。
耗時排名是排在比較後面的，這也說明了還有更優的解法。

空間換時間

此題關鍵的地方在於：如何快速的找到 j，暴力枚舉在最壞的情況下會找遍整個數組，直到最後一個才找到，時間複雜度也就是 O(n)。

那麼，在這裡我們可以利用 哈希演算法 進行映射，從而達到更快查找效率。理論上 哈希演算法 設計良好的情況下可以達到常數級 O(1) 的複雜度。

一個例子：在值不大的情況下，可以用值當做數組下標，而數組的值作為原來數組的下標。即：

對於 x = nums[i]，存在 hash[x] = i。這樣在犧牲大量空間的情況下可以使得查詢效率達到極致的常數級 O(1)。

但是很遺憾，這道題並沒有辦法直接使用這個方法，因為 int.MaxValue 是遠超過了數組可以定義的範圍。編譯時會報錯，記憶體溢出。

既然暫時沒有辦法達到 O(1) 的地步，那麼可以考慮使用實現了 哈希演算法 （這裡保留說法，若羽源碼沒有閱讀完，在看到index的取法有著很明顯的哈希痕迹進行猜測的）的 Dictionary<TKey, TValue>。

程式碼：

public class Solution  {      public int[] TwoSum(int[] nums, int target)      {          var dic = new Dictionary<int, List<int>>();          for(int i = 0; i < nums.Length; i ++)          {              int num = nums[i];              int res = target - num;              if(dic.ContainsKey(res))              {                  return new int[] {i, dic[res][0]};              }                if(!dic.ContainsKey(num))              {                  dic.Add(num, new List<int>(){});                }                dic[num].Add(i);          }          return new int[] {};      }  }

執行用時：468 ms
記憶體消耗：30.5MB
用時排名：超過78.61%

改進後的演算法排名與之前可謂是天差地別，已經到了前 30%。

僅僅是達到了前三分之一，說明這個演算法還有可以更進一步的優化。

進一步優化查詢

這裡用了 Dictionary, 但這裡的 TValue 是一個列表。仔細想想，這裡我們是不需要保存列表的，只需要保存一個值即可，因為只需要找到一組答案即可！

其次可以減去第二個判斷，並不需要判斷是否存在，直接覆蓋/新建即可。

最後可以反向查詢，查之前的數值中是否缺一個 nums[i]，對應存進去的就是差值，這樣可以減去兩個臨時變數，順帶優化一點點的空間。

程式碼：

public class Solution  {      Dictionary<int, int> dic = new Dictionary<int, int>();      public int[] TwoSum(int[] nums, int target)      {          if(nums.Length == 2) return new int[] {0, 1};          dic.Clear();          for (int i = 0; i < nums.Length; i++)          {              if(dic.ContainsKey(nums[i])) return new int[] {dic[nums[i]], i};              dic[target - nums[i]] = i;          }          return new int[] { };      }  }

執行用時：360 ms
記憶體消耗：30MB
用時排名：超過98.83%

改進後的演算法相比之前的差距並不是非常的大，但就是這百來毫秒的差距，排名上升到了前 3%。

這個演算法還是有可以改進的地方，但是若羽現在暫時還沒有思路如何再進一步將查詢複雜度降下去，這裡可能需要自己實現一個更高效的哈希演算法。

寫在最後

許久沒有接觸演算法了，有些生疏，思路上也有些堵塞。這裡若羽對於接下來進一步優化有一些初步的想法，待有空實驗後再加一篇解題報告。

分段策略，當數據量達到一定程度時使用更高效的演算法，當數據量較小時，可能哈希耗時會更長一些，這個需要實驗。大意便是尋找多個演算法的耗時閾值，利用閾值進行策略選擇。
自己實現針對題目更高效的哈希演算法。