LeetCode --- 1. Two Sum

題目鏈接：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

這道題的要求是在數組中找到兩個數字使其之和等於給定的數字，然後返回這兩個數字的索引（就是數組下標加1哦）。思路如下：

1. 暴力查找

這是最簡單直接的方式，兩層循環遍歷數組。不上代碼了。。。

時間復雜度：O(n2)

空間復雜度：O(1)

2. 排序後查找

首先對數組排序。不過由於最後返回兩個數字的索引，所以需要事先對數據進行備份。然後采用2個指針l和r，分別從左端和右端向中間運動：當l和r位置的兩個數字之和小於目標數字target時，r減1；當l和r位置的兩個數字之和大於目標數字target時，l加1。因此只需掃描一遍數組就可以檢索出兩個數字了。最後再掃描一遍原數組，獲取這兩個數字的索引。

時間復雜度：O(nlogn)（取決於排序時間復雜度）

空間復雜度：O(n)（取決於排序空間復雜度以及備份數組的空間復雜度）

 1 class Solution{
 2 public:
 3     vector twoSum(vector &numbers, int target)
 4     {
 5         vector v(numbers);
 6         sort(v.begin(),v.end());
 7         
 8         int l = 0, r = v.size() - 1;
 9         while(l < r)
10         {
11             if(v[l] + v[r] == target)
12                 break;
13             else if(v[l] + v[r] > target)
14                 -- r;
15             else
16                 ++ l;
17         }
18         
19         vector index;
20         for(int i = 0, n = 2; i < numbers.size(); ++ i)
21             if(v[l] == numbers[i] || v[r] == numbers[i])
22             {
23                 index.push_back(i + 1);
24                 if(-- n == 0)
25                     break;
26             }
27         
28         return index;
29     }
30 };

3. Hash表

對每個出現的數字存入Hash表（set）中，這樣可以以O(1)的時間判斷每個數字是否在數組中出現過。因此只需要遍歷一次數組即可。

時間復雜度：O(n)

空間復雜度：O(n)

 1 class Solution{
 2 public:
 3     vector twoSum(vector &numbers, int target)
 4     {
 5         vector v;
 6         map m;
 7         for(int i = 0; i < numbers.size(); ++ i)
 8         {
 9             if(m.find(target - numbers[i]) != m.end())
10             {
11                 v.push_back(m[target - numbers[i]] + 1);
12                 v.push_back(i + 1);
13                 break;
14             }
15             m[numbers[i]] = i;
16         }
17         return v;
18     }
19 };

耶，第1道，加油。。。^_^