# 2 Sum

## Question

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.

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 - 哈希表

### C++

class Solution {
public:
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1+1, index2+1] (index1 < index2)
*/
vector<int> twoSum(vector<int> &nums, int target) {
vector<int> result;
const int length = nums.size();
if (0 == length) {
return result;
}

// first value, second index
unordered_map<int, int> hash(length);
for (int i = 0; i != length; ++i) {
if (hash.find(target - nums[i]) != hash.end()) {
result.push_back(hash[target - nums[i]]);
result.push_back(i + 1);
return result;
} else {
hash[nums[i]] = i + 1;
}
}

return result;
}
};


### 源碼分析

1. 異常處理。
2. 使用 C++ 11 中的哈希表實現unordered_map映射值和索引。
3. 找到滿足條件的解就返回，找不到就加入哈希表中。注意題中要求返回索引值的含義。

### Python

class Solution:
"""
@param numbers : An array of Integer
@param target : target = numbers[index1] + numbers[index2]
@return : [index1 + 1, index2 + 1] (index1 < index2)
"""
def twoSum(self, numbers, target):
hashdict = {}
for i, item in enumerate(numbers):
if (target - item) in hashdict:
return (hashdict[target - item] + 1, i + 1)
hashdict[item] = i

return (-1, -1)


### 源碼分析

Python 中的dict就是天然的哈希表，使用 enumerate 可以同時返回索引和值，甚為方便。按題意似乎是要返回 list, 但個人感覺返回 tuple 更為合理。最後如果未找到符合題意的索引，返回(-1, -1).

## 題解2 - 排序後使用兩根指針

### C++

class Solution {
public:
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1+1, index2+1] (index1 < index2)
*/
vector<int> twoSum(vector<int> &nums, int target) {
vector<int> result;
const int length = nums.size();
if (0 == length) {
return result;
}

// first num, second is index
vector<pair<int, int> > num_index(length);
// map num value and index
for (int i = 0; i != length; ++i) {
num_index[i].first = nums[i];
num_index[i].second = i + 1;
}

sort(num_index.begin(), num_index.end());
int start = 0, end = length - 1;
while (start < end) {
if (num_index[start].first + num_index[end].first > target) {
--end;
} else if(num_index[start].first + num_index[end].first == target) {
int min_index = min(num_index[start].second, num_index[end].second);
int max_index = max(num_index[start].second, num_index[end].second);
result.push_back(min_index);
result.push_back(max_index);
return result;
} else {
++start;
}
}

return result;
}
};


### 源碼分析

1. 異常處理。
2. 使用length保存數組的長度，避免反複調用nums.size()造成性能損失。
3. 使用pair組合排序前的值和索引，避免排序後找不到原有索引信息。
4. 使用標準庫函數排序。
5. 兩根指針指頭尾，逐步靠攏。

### 複雜度分析

Note lintcode 上的題要求時間複雜度在 $O(n \log n)$ 時，空間複雜度為 $O(1)$, 但問題是排序後索引會亂掉，如果要保存之前的索引，空間複雜度一定是 $O(n)$，所以個人認為不存在較為簡潔的 $O(1)$ 實現。如果一定要 $O(n)$ 的空間複雜度，那麼只能用暴搜了，此時的時間複雜度為 $O(n^2)$.