## Two Sum 問題

### 一、Two Sum 問題

Leetcode OJ - Two Sum Problem : https://leetcode.com/problems/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

### 二、Two Sum 問題詳解

#### 1. Hash Table 解：使用 C++ 的 map

class Solution {
public:
// Two Sum Solution
//      @ Total Complexity : O(NlogN), where N is nums size
//      @ FIND() operator in map :  O(logN), key look up in red black tree

vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> hashTable;
map<int,int>::iterator iter;
vector<int> ansIndex(2);

for(int i = 0; i < nums.size(); i++){
int x = nums[i];
iter = hashTable.find(target - x);

if(iter != hashTable.end()){
ansIndex[0] = iter->second + 1;
ansIndex[1] = i + 1;
return ansIndex;
}
else
hashTable[x] = i;
}

}
};


#### 2. 陣列解：使用 C++ 的 vector

class Solution {
public:
// Two Sum Solution
//      @ Total Complexity : O(NlogN)
//      @ SORT() : O(NlogN)

struct sort_pred {
bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right{
return left.first < right.first;
}
};

const int reserveNum = 1024;

vector<int> twoSum(vector<int>& nums, int target) {
vector< pair<int, int> > numList;
vector<int> ansIndex(2);
numList.reserve(reserveNum);

for(int i = 0; i < nums.size(); i++)
numList.push_back(make_pair(nums[i] ,i));

sort(numList.begin(), numList.end(), sort_pred());

int i = 0, j = nums.size()-1;

while(i < j){
int sum = numList[i].first + numList[j].first;
if(sum < target)
i++;
else if (sum > target)
j--;
else{
if(numList[i].second < numList[j].second){
ansIndex[0] = numList[i].second+1;
ansIndex[1] = numList[j].second+1;
}
else{
ansIndex[0] = numList[j].second+1;
ansIndex[1] = numList[i].second+1;
}
return ansIndex;
}
}

}
};


1. Hash Table 解

2. 陣列解

### References

Leetcode OJ - Two Sum Problem
https://leetcode.com/problems/two-sum/

【心得】C++ STL-Introduction to pair<T1, T2>
http://forum.gamer.com.tw/Co.php?bsn=60292&sn=3518

Stackoverflow - use a custom comparator
http://stackoverflow.com/questions/279854/how-do-i-sort-a-vector-of-pairs-based-on-the-second-element-of-the-pair