# leetCode[003]Two Sum

### 题目1： Two Sum 1

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

####题意：

####关键点：

class Solution{
public:
// O(n) runtime, O(n) space
// We could reduce the runtime complexity of looking up a value to O(1) using a hash map that maps a value to its index.
std::vector<int> twoSum(std::vector<int>& numbers, int target){
std::vector<int> vecRet;
std::map<int, int> mapIndex;
for (size_t i = 0; i < numbers.size(); ++i){
if (0 != mapIndex.count(target - numbers[i])){
int nIndex = mapIndex[target - numbers[i]];
// 当前存储的Index肯定比i要小，注意要排除i
if (nIndex < i){
vecRet.push_back(nIndex + 1);
vecRet.push_back(i + 1);
return vecRet;
}
} else {
mapIndex[numbers[i]] = i;
}
}
return vecRet;
} // twoSum
};


leetCode的OJ系统评判结果如下所示：

### 题目2：Two Sum 2

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. 数组既然排序，元素之前的大小关系相对确定，存在的这一对元素必然处于相对固定的位置，我们可以使用两个游标，一个从头部遍历，一个从尾部遍历，两者所指元素之和如果偏大，调整后面的游标，相反则调整前面的游标。
2. 由于两个int之和有可能出现INT_MAX的情况，所以如果输入类型给定int，则我们需要使用long long类型来表示才能避免出现溢出的情况。

class Solution{
public:
std::vector<int> twoSum(std::vector<int> &numbers, int target){
std::vector<int> vecRet;
int nLeft = 0;
int nRight = numbers.size() - 1;

while (nLeft < nRight){
// 小心两个int之和溢出，使用long long类型
long long int nAdd = numbers[nLeft] + numbers[nRight];
if (nAdd == target){
vecRet.push_back(nLeft + 1);
vecRet.push_back(nRight + 1);

return vecRet;
}
else if (nAdd > target){
nRight--;
}
else if (nAdd < target){
nLeft++;
}
}

return vecRet;
}
};