问题
Given an array of integers that is already sorted in ascending order, 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 and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
思路
数组存在重复元素的情况，使用insert，map始终保存第一个值。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
unordered_map<int, int> m;
vector<int> res;
int other = 0;
for(int i = 0; i < numbers.size(); ++i)
{
pair<int, int> val(numbers[i], i);
m.insert(val);
//m.insert(make_pair<int, int>(numbers[i], i)); 编译报错，不支持此写法
other = target - numbers[i];
if(m.find(other) != m.end() && m[other] != i)
{
res.push_back(m[other] + 1);
res.push_back(i + 1);
return res;
}
}
return res;
}
};
上面的解法，需要额外的map空间。下面的解法，双指针移动。空间复杂度为O(1)若数组原为乱序，先排序再双指针，可解两数相加和I
C++小知识
unordered_map::insert几种插入方式，可直接数组形式插入
find函数返回迭代器