1. 题目

两数之和II

2. 题意

有序数组，找到两数和为一固定值的两数下标。要求只能用到常数的空间。

3. 题解

与两数之和的区别是排好序了，且不能用额外的空间。即不能使用哈希表了，二重循环时间复杂度会超。

3.1 二分

固定指针左端，二分查找指针右端

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {vector<int> res;int sz = numbers.size();for ( int i = 0; i < sz - 1; ++i) {int l = i + 1;int r = sz - 1;if ( numbers[i] + numbers[r] < target)continue;int fVal = target - numbers[i];while ( l <= r) {int mid = (l + r) >> 1;if ( fVal > numbers[mid])l = mid + 1;else if ( fVal < numbers[mid])r = mid - 1;else {res = { i + 1, mid + 1};break;}}if ( res.size())break;}return res;}
};

3.2 双指针

左指针在最左端，右指针在右端；
和大于指定值则左移右指针，小于则右移左指针。

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int l = 0;int r = numbers.size() -1;while ( l < r) {if ( numbers[l] + numbers[r] > target) {r--;}else if (numbers[l] + numbers[r] < target) {l++;}else {return { l + 1, r + 1};break;}}return {};}
};