Leetcode是許多歐美IT公司招聘工程師會先用的算法題庫，雖然不盡是原題，但是基本也是小改動後的類似題。學習算法最重要的是不斷積累，我們從今天開始 每天一道算法題，包括：
算法解題總結：
- 問題分析
- Trick思考，
- Corner Case測試，
- 時間複雜度/空間複雜度分析，
- 優化和總結
LeetCode Q1: Two Sum
問題描述：
給你一個整數數組int[]，和一個目標值target,數組中肯定存在一個唯一解能夠使得兩個不同下標的元素x1,x2的算術和等於target. 相同的元素只能使用一次，不能重複使用。
問題分析：
-1.題目沒說數組是有序的，雖然例子給的恰好是有序的
-2.要求的是元素下標，不是元素本身，所以直接排序數組的話，元素下標會亂掉
-3.數組中元素可能存在重複值
-4.O(n^2)肯定是可以的，但是有沒有更優的解呢？
解決方案：
Solution 1: Brute Force 雙循環 / 時間複雜度=O(n^2) 不需要額外的空間
使用兩個指針，i和j，固定i，移動j往右掃描直到找到結果，代碼如下：
可以看到最簡單的雙循環基本是最慢的-70ms，提交後處於後10%的分佈。那有沒有更快的方法呢？答案是solution 2
Solution 2: 使用HashMap存儲index,從而空間換時間 / 時間複雜度=O(n) 空間複雜度=O(n)
先用HashMap遍歷一邊數組O(n)，保存下來每個元素的值和對應的下標index; 然後重新用另外一個循環遍歷所有的值o(n)，當前值就是x, 那需要找的另外一個值就是target-x. 理亂上我們只需要遍歷數組元素的一半就可以結束了。此處需要注意，因為可能存在多個相同的元素，所以我們哈希表裡面存儲index要使用list.
使用哈希表後，運行速度得到了明顯提升20ms,速度提升了3倍，基本上達到了O(n)的最優解。類似的問題還會有 Three Sum 等等，後序持續更新中!
總結：
當遇到問題是，如果沒有頭緒的情況下，可以先嚐試用暴力破解的方法，然後慢慢優化。Do is better than perfect,永遠先搞一個work的方案出來，別老是想著一步到位，直接最優解。
關注，轉發和收藏“松鼠遊學”，每日更新 "Leetcode" 算法相關的面試題和解題方案並附上源碼，歡迎有興趣的小夥伴私信私聊！
@極限尤可突破，至臻亦不可止!
閱讀更多 松鼠遊學 的文章
