[LC1] Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

題目要求：

給定一個integer array以及一個target value，找出兩個數字，他們的總和等於給定的target value，並且return他們的index。假設可以找到唯一的一組solution.

思路：

暴力法是依序抓兩個數來相加，如果結果等於target，即找到答案，但time complexity會是O(n^2)，太慢了。

另一種想法是，藉由hash table lookup只要O(1)的優勢，把對應的index找出來，速度會快很多。舉個例子：假設 a and b兩數是答案，因為 a + b = target，所以 b = target - a。然後我們在hash table裡面存的 Key是 array data, Value是 data index，

Array:

Index  0     1     2     3
Data    2     7   11   15

Hash Table:

Key     2     7     11     15
Value  0     1       2       3

假設 target是 9，用一個 loop讓 array data輪流當 a, 假設現在 a是 index 0的 2，9 - 2 = 7，問題變成 hash key是 7，請從 hash table中找對應的 hash value，就會得到 index 1，結束。One pass即可找到答案，time complexity = O(n), Space complexity = O(n)。
特別注意答案要求的 index是 1 base，所以 return之前務必先都加 1。

實作：

C++11的STL：unordered_map實作 hash table，並且可以使用中括號直接用 hash key當 index來存取 hash value。所以選他來當成解法中的 hash table。

http://www.cplusplus.com/reference/unordered_map/unordered_map