167. 两数之和 II - 输入有序数组
题目描述
输入整数数组 numbers，它已按非递减顺序排好，下标从 1 开始计。再输入目标值 target。
找出两个不同位置 index1 和 index2，要求 index1 小于 index2，且两处的数之和等于 target。同一个元素不能用两次。
返回 [index1, index2]。题目保证恰有一组答案。你的解法只能使用常数大小的额外空间。
示例 1
输入：numbers = [2,7,11,15], target = 9 输出：[1,2]
解释：2 + 7 = 9，它们位于第 1、2 个位置。
示例 2
输入：numbers = [2,3,4], target = 6 输出：[1,3]
解释：2 + 4 = 6，位于第 1 和第 3 个位置。
示例 3
输入：numbers = [-1,0], target = -1 输出：[1,2]
解释：-1 + 0 = -1，位于第 1、2 个位置。
数据范围
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbers按非递减顺序排列。-1000 <= target <= 1000- 有且只有一个合法答案。
解题思路：双指针
左右双指针 i=0、j=n-1。和 s 太小，只能增大较小的数，i += 1；太大则 j -= 1。每次移动都排除了一整行或一整列的组合：s < target 时 numbers[i] 配任何 <= j 的数都不够大。本题也可枚举 i 后二分找 target - numbers[i]，但双指针是 O(n)。
为什么正确
若答案为 (p, q)，则始终有 i <= p 且 q <= j。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
返回的下标要 +1；不要用哈希表，题目要求常量空间。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i, j = 0, len(numbers) - 1
while i < j:
s = numbers[i] + numbers[j]
if s == target:
return [i + 1, j + 1]
if s < target:
i += 1
else:
j -= 1
return []class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int s = numbers[i] + numbers[j];
if (s == target) {
return new int[]{i + 1, j + 1};
}
if (s < target) {
i++;
} else {
j--;
}
}
return new int[0];
}
}class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int i = 0, j = numbers.size() - 1;
while (i < j) {
int s = numbers[i] + numbers[j];
if (s == target) {
return {i + 1, j + 1};
}
if (s < target) {
i++;
} else {
j--;
}
}
return {};
}
};func twoSum(numbers []int, target int) []int {
i, j := 0, len(numbers)-1
for i < j {
s := numbers[i] + numbers[j]
if s == target {
return []int{i + 1, j + 1}
}
if s < target {
i++
} else {
j--
}
}
return []int{}
}var twoSum = function(numbers, target) {
let i = 0, j = numbers.length - 1;
while (i < j) {
const s = numbers[i] + numbers[j];
if (s === target) {
return [i + 1, j + 1];
}
if (s < target) {
i++;
} else {
j--;
}
}
return [];
};function twoSum(numbers: number[], target: number): number[] {
let i = 0, j = numbers.length - 1;
while (i < j) {
const s = numbers[i] + numbers[j];
if (s === target) {
return [i + 1, j + 1];
}
if (s < target) {
i++;
} else {
j--;
}
}
return [];
}其他解法
二分查找对每个数单独找另一半，是 O(n log n)；双指针利用单调性每步排除一个数，是 O(n)。
解法 2：二分查找 时间 O(n log n)，空间 O(1)
枚举第一个数的下标 i。在右侧区间 [i+1, n-1] 中二分查找 target - numbers[i]。找到就返回两个下标加一。
直接利用数组有序，容易想到。比双指针多一个 log n 因子。
from typing import List
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
n = len(numbers)
for i in range(n):
want = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == want:
return [i + 1, mid + 1]
if numbers[mid] < want:
lo = mid + 1
else:
hi = mid - 1
return []class Solution {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
for (int i = 0; i < n; i++) {
int want = target - numbers[i];
int lo = i + 1, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (numbers[mid] == want) return new int[]{i + 1, mid + 1};
if (numbers[mid] < want) lo = mid + 1;
else hi = mid - 1;
}
}
return new int[0];
}
}class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
for (int i = 0; i < n; i++) {
int want = target - numbers[i];
int lo = i + 1, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (numbers[mid] == want) return {i + 1, mid + 1};
if (numbers[mid] < want) lo = mid + 1;
else hi = mid - 1;
}
}
return {};
}
};func twoSum(numbers []int, target int) []int {
n := len(numbers)
for i := 0; i < n; i++ {
want := target - numbers[i]
lo, hi := i+1, n-1
for lo <= hi {
mid := (lo + hi) / 2
if numbers[mid] == want {
return []int{i + 1, mid + 1}
}
if numbers[mid] < want {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
return []int{}
}var twoSum = function(numbers, target) {
const n = numbers.length;
for (let i = 0; i < n; i++) {
const want = target - numbers[i];
let lo = i + 1, hi = n - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (numbers[mid] === want) return [i + 1, mid + 1];
if (numbers[mid] < want) lo = mid + 1;
else hi = mid - 1;
}
}
return [];
};function twoSum(numbers: number[], target: number): number[] {
const n = numbers.length;
for (let i = 0; i < n; i++) {
const want = target - numbers[i];
let lo = i + 1, hi = n - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (numbers[mid] === want) return [i + 1, mid + 1];
if (numbers[mid] < want) lo = mid + 1;
else hi = mid - 1;
}
}
return [];
};