[LeetCode] 1. Two Sum 兩數之和

Part 1. 題目描述 (easy)

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.

Example: 

Given nums = [2, 7, 11, 15], target = 9, because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Part 2. 分析

 本題是LeetCode的第一題，求解題目並不難，但是如何進一步優化時間複雜度是本題的重點。需要用到的基礎是hash table，在python中可以用字典來實現。

Part 3. 解決方案

【方法1: 暴力求解 (Brute Force)】

 最簡單直接的求解方式，遍歷所有兩個數的組合，將兩數之和跟target的值進行比較。時間複雜度O(n²)，空間複雜度O(1)。

 python 代碼如下：

1 class Solution:
2     def twoSum(self, nums, target):
3         for i in range(len(nums)):
4             for j in range(i+1, len(nums)):
5                 if nums[i] + nums[j] == target:
6                     return [i, j]

【方法2: One-pass Hash Table】

如果我們想要降低時間複雜度，該如何解決呢？我們可以藉助hash函數來實現，因為它可以免除了第二輪的遍歷過程，使搜索時間變為O(1)，總的時間複雜度降低為O(n)。但相應的，其空間複雜度會變複雜，變為O(n)。

python 代碼如下：

1 class Solution:
2     def twoSum(self, nums, target):
3         dict_nums = {}   # key: num  values: index
4         for i in range(len(nums)):
5             rest = target - nums[i]
6             if rest in dict_nums:
7                 return [dict_nums[rest], i]
8             dict_nums[nums[i]] = i

備註：註意判斷hash中是否存在需要的數字(line 5-7)和添加新數字到hash中(line 8)的順序，如果反過來寫，某些case會出錯，比如nums = [3,3,1,4], target = 6. 因為在hash中，我們將數字作為key來存儲，這要求key是唯一的。如果我們先執行存儲操作的話，當出現2個相同數字的時候就會報錯。

Part 4. 心得體會 

       剛開始接觸LeetCode，想通過刷演算法題的方法把演算法、數據結構的基礎知識好好鞏固一番。因為主要不是為了面試而刷題，所以做題順序上可以更隨心所欲一些。準備先做top 100的題目，然後其餘的題目順序待定。編程語言準備以python為主，雖然java、C++都用過，但是都沒有到熟練掌握的程度。因為以後可能更多的會用python來做實驗，所以正好這回多寫點python程式，提升代碼水平，希望自己能堅持下去咯！

       完事開頭難，這一題雖然是easy級別的，但是自己在第一次寫暴力求解代碼的時候還是粗心出了錯，腦子有點跟不上節奏啊......在學習方法2的時候，因為對python字典不怎麼瞭解，還花時間去學習了字典的基本操作。再加上這是我第一次在博客上寫技術的東西(以前都是私底下用有道筆記)，所以花了不少時間，但是已經從中感受到樂趣啦。