# LeetCode167. Two Sum II - Input array is sorted（思维）

## LeetCode167. Two Sum II - Input array is sorted（思维）

• Easy
• Accepted：203,351
• Submissions：416,166

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.

### Note

• You may assume that each input would have exactly one solution and you may not use the same element twice.

### Example

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

### 链接

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

### 题解

• 暴力解法就不说了。
• 题目说了有序，所以可以使用二分查找，对于一个数a[i]，找另一个数target-a[i]是否在这个数组中，两个数的下标不同，使用二分会有一个问题，如果出现{2, 3, 3} 6这种情况，二分找到的数target-a[i]的下标和a[i]的下标相同，所以需要分类讨论下，看是否存在重复元素。时间复杂度$O(nlogn)$。
• 还有一种解决方法就是用unordered_map来存元素和下标间的映射关系，常数时间查询，但是注意有一个隐藏的bug，当出现相同的元素时会保留后面一个元素的键值关系，但是因为从前往后遍历且答案唯一所以能AC。

### 代码

• Runtime: 4 ms, faster than 99.00% of C++ online submissions for Two Sum II - Input array is sorted.
• Memory Usage: 1.6 MB, less than 66.67% of C++ online submissions for Two Sum II - Input array is sorted.
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int len = numbers.size();
vector <int> ans;
for (int i = 0; i < len; ++i)
{
int x = target - numbers[i];
int pos = binarySearch(numbers, x);
if (pos != -1)
{
// 存在数值相同元素
if (pos == i && i < len - 1 && numbers[i] == numbers[i + 1])
{
ans.push_back(i + 1);
ans.push_back(i + 2);
}
else if (pos != i)
{
ans.push_back(i + 1);
ans.push_back(pos + 1);
}
break;
}
}
return ans;
}

// 二分查找
int binarySearch(vector<int>& numbers, int x)
{
int l = 0, r = numbers.size(), m;
while (l <= r)
{
m = l + (r - l) / 2;
if (x == numbers[m])
return m;
if (x > numbers[m])
l = m + 1;
else
r = m - 1;
}
return -1;
}
};
//     Accepted    4 ms    1.6 MB

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map <int, int> ump;
vector <int> ans;
int len = nums.size(), tmp;
for (int i = 0; i < len; ++i) // 建立映射关系
ump[nums[i]] = i;
for (int i = 0; i < len; ++i)
{
tmp = target - nums[i];
if (ump.count(tmp) && ump[tmp] != i) // 存在target-a[i]且不为同一个数
{
ans.push_back(i + 1);
ans.push_back(ump[tmp] + 1);
break;
}
}
return ans;
}
};

### 拓展

// Accepted    4 ms 1.6 MB
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int len = numbers.size();
vector <int> ans;
int l = 0, r = len - 1;
while (l < r)
{
if (numbers[l] + numbers[r] == target)
{
ans.push_back(l + 1);
ans.push_back(r + 1);
break;
}
else if (numbers[l] + numbers[r] < target)
l++;
else if (numbers[l] + numbers[r] > target)
r--;
}
return ans;
// throw invalid_argument("No solution.")
}
};

The end.
2019年2月3日 星期日