1. Two Sum - 兩周前做過，回來看還是沒辦法一次做出來

第一次寫medium

第一次把自己的心得Publish出來，契機是來自huli大大的文章。期望未來的自己回來看的時候可以深刻的回憶起這些東西，不管是覺得好笑，還是恍然大悟這題的解法，都會是有意義的。文章就是照著自己的想法簡簡單單的寫出來，不想花太多時間琢磨，因為是自己的心得筆記。如果路過的讀者有幸獲得一點點收穫，那我也會很開心的。

每一篇心得都有價值——為什麼初學者才更應該要寫心得筆記

記得大二的時候就寫過leetcode，那時候寫沒幾題，就空了兩年，再回來已經是大四了。寫論文之前也是非常斷斷續續的寫LC，直到寫完論文開始做面試準備的時候才真的認真面對。解題的時候我其實是享受的，比起準備Behavioral question (BQ)，我更喜歡解LC，BQ練一練都會想睡，好無聊，解題有趣多了，還能更加深Data Structure and Algorithms(DSA)的概念，雖然偶爾看著題海，自己只有不到50題左右，90%還忘光的情況下，現在回來看天字第一題還是不會，難免會有些挫折。

但，難道我就這樣不準備了嗎?當然不可能，既然不可能，就乖乖寫吧。這段話我可能要看上萬次🤣每次崩潰的時候都回來看一下。

正題

1. Two Sum

最近每天都有寫兩題leetcode，簡單到複雜的都有寫過，兩周過去後再回來寫天字第一題，還是沒寫出來。甚至題目都沒完全搞懂，一開始還直接sort了一下，五分鐘內寫完，run，爆炸。才發現我是需要return原本array的index，sort完後就跟原本的不同了。

於是怎麼辦呢，想不到，一直覺得是2 pointers，因為最熟就2 pointers，而且也簡單😂完全沒考慮到HashMap的部分。想了幾分鐘看upvote最高的解法才恍然大悟，對耶HashMap的搜尋是O(N)既可以拿來解決問題，還能優化時間。因為題目有個follow-up是想出比O(N²)更快的解法。

而HashMap怎麼解決問題呢，循環每一個nums的element的時候都算一下他的complement，也就是總數減掉其中一個數後，剩餘的那個數。這樣只要在HashMap找到complement的時候就可以同時知道第一個數，和第二個數的位置，因為其中一個數就是我們疊代到的數字，另一個直接搜尋一下.get(complement)得到他的index，回傳數組就OK了。

方法

1. 建立一個HashMap

2. 開始疊代數組nums，每個element為num

3. 算每個num的complement

4. 如果有在HashMap找到complement的話，取出他的index

5. 和當前num組成數組，回傳

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; ++i) {
            int complement = target - nums[i];

            // Found the pair
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            // If not found, store it
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}

參考解答

leetcode