167. 两数之和II-输入有序数组#

题目描述#

题目链接: LeetCode 167

给你一个下标从 1 开始的整数数组 numbers，该数组已按 非递减顺序排列，请你从中找出满足相加之和等于目标数 target 的两个数。返回这两个数的下标（从 1 开始）。

示例：

1
输入：numbers = [2,7,11,15], target = 9
2
输出：[1,2]
3
解释：2 与 7 之和等于目标数 9，下标从 1 开始对应 [1,2]。

解题思路#

核心思想#

利用数组有序这一条件，采用相向双指针。两个指针所指元素的和为 s，通过与 target 比较来决定指针移动方向：

s < target：和偏小，需要更大的数 → 左指针右移；
s > target：和偏大，需要更小的数 → 右指针左移。

每轮必然向目标收敛，因此可以在 O(n) 内找到答案，无需哈希表（题目的进阶要求 O(1) 空间恰好可由双指针达成）。

算法步骤#

left = 0, right = n - 1
当 left < right 时循环：
- 记 s = numbers[left] + numbers[right]
- s == target：返回 [left + 1, right + 1]
- s < target：left += 1
- s > target：right -= 1

逐步举例#

numbers = [2,7,11,15], target = 9

right	和 s	操作
3	17	`>9` → `right=2`
2	13	`>9` → `right=1`
1	9	`==9` → 返回 `[1,2]`

复杂度分析#

时间复杂度：O(n)，每个元素只被访问一次
空间复杂度：O(1)，只用了两个指针

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
6
        left, right = 0, len(numbers) - 1
7
        while left < right:
8
            s = numbers[left] + numbers[right]
9
            if s == target:
10
                return [left + 1, right + 1]
11
            if s < target:
12
                left += 1
13
            else:
14
                right -= 1
15
        return []

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5

6
import unittest
7

8
from solution import Solution
9

10

11
class Test167(unittest.TestCase):
12
    def test_example1(self):
13
        self.assertEqual(Solution().twoSum([2, 7, 11, 15], 9), [1, 2])
14

15
    def test_example2(self):
16
        self.assertEqual(Solution().twoSum([2, 3, 4], 6), [1, 3])
17

18
    def test_example3(self):
19
        self.assertEqual(Solution().twoSum([-1, 0], -1), [1, 2])
20

21

22
if __name__ == '__main__':
23
    unittest.main()