LeetCode 1. Two Sum

身為一位碼農不免俗總是要刷刷 LeetCode，一方面培養自己在工作上的演算法功力，另一方面在面試時也有很大的機會會被問到。

有刷 LeetCode 這個想法一段時間了，身邊也有不少朋友有在刷，也因為之後想要舉辦一個刷 LeetCode 的讀書會，想說我自己先來嘗試嘗試，並思考一下這個讀書會可以進行的流程。

# Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

這是 LeetCode 的第一題，不用說難度當然是 Easy。先從最簡單的下手才不會一開始就感到滿滿的挫折，先建立起自信心才能迎接後面困難的挑戰。

題目的描述是，給你一個數字陣列，並回傳其相加總和為目標值的索引陣列。P.S. 陣列元素不可被重覆使用，意即每個元素只能使用一次。

一開始我的想法很直覺也很簡單，依照題目的敘述，我只要寫個巢狀迴圈就能解決。第一層迴圈跑第一個數字，第二層迴圈跑第二個數字，當兩個數字的總和等於目標值就回傳索引值。於是我的代碼 (JavaScript) 如下。

事情不是像憨人想得這麼簡單，這是個最直覺的解法但卻不最好的解法。兩層的迴圈會讓時間複雜度變成 O(n²)，於是乎我開始思考如何把時間複雜度降為 O(n) 。

老實說這個思考轉換的過程蠻辛苦的，動腦是一回事，但重點在於如何改變思考模式，我覺得這才是刷題帶給我最大的吸引力。

把話題拉回來，要降低時間複雜度，在這邊就是要只用一個迴圈，我需要一個工具才能達成這個需求。那就是使用 Hash 。Hash 是個 (key, value) 的結構，它可以拿來做資料比對，剛好符合這題的使用情境。(若對 Hash 不熟或是想要複習可以參考這裡)

我先宣告一個 Hash，在迴圈中判斷每個值有沒有存在 Hash 裡，若有則回傳索引值，若沒有則把這個值加入 Hash。這邊比較要注意的重點是 Hash 的使用方式，請看第六行。我把目標值減掉陣列值的結果當成 Hash 的 key，並把迴圈的索引當成 Hash 的 value，這樣才能達成第四行的 if 判斷式。

# 結語

刷 LeetCode 蠻好玩，但也蠻累的。我希望能夠像寫文章一樣持續下去，藉此養成並保持這個習慣。我不會每一題都刷，畢竟蠻浪費時間的。之後應該會以刷難度 medium 為主，簡單的題目可能就不會寫成文章了。

#參考資料

白話的 Hash Table 簡介

https://blog.techbridge.cc/2017/01/21/simple-hash-table-intro/