Python算法训练序列
双指针与滑动窗口 · Unit 03
← Unit 02
167
LeetCode 167Two Sum II · 两数之和 II
排序不是背景条件，
而是每次安全排除一端的证据。
如果当前两端之和偏小，最小值不可能与区间内任何更小的右值达到目标，因此可以排除左端；如果当前和偏大，最大值不可能与区间内任何更大的左值达到目标，因此可以排除右端。
LeetCode #167 原题内容
中文转述 · 示例、约束与提交签名
题目要求
给定一个按非递减顺序排列、题意上使用 1-based 下标的整数数组 numbers，找到两个不同位置，使对应元素之和等于 target。返回这两个位置组成的数组，并保证恰好存在一个解。算法只能使用常数额外空间。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
# 返回 [left + 1, right + 1]
约束
2 ≤ len(numbers) ≤ 30000-1000 ≤ numbers[i], target ≤ 1000numbers按非递减顺序排列；- 恰好存在一个答案，且同一元素不能使用两次。
示例
numbers = [2,7,11,15], target = 9
输出：[1,2]
输出：[1,2]
numbers = [2,3,4], target = 6
输出：[1,3]
输出：[1,3]
numbers = [-1,0], target = -1
输出：[1,2]
输出：[1,2]
索引提醒
Python列表内部仍用 0-based 索引；只有返回答案时才统一加 1。
1. 体验组合枚举
2. 发现单调方向
3. 证明安全排除
4. 代码联动
5. 批量计数迁移
演示：numbers = [1,2,4,6,8,11]，target = 10等待判断
numbers[left]1
+
numbers[right]11
=
current_sum12
12 > 10：和偏大
当前循环不变量
若答案尚未找到，则答案一定仍位于[left, right]的未排除区间中。
当前移动依据
当前和偏大时，排除右端；当前和偏小时，排除左端。
left0
right5
当前和12
已排除端点0
返回下标—
候选配对空间
每次排除一个端点，等价于一次删除一整行或一整列候选配对。
补全 LeetCode 提交代码卡住可查看参考答案
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right =
while left < right:
current_sum =
if current_sum == target:
return
if current_sum < target:
else:
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
if current_sum < target:
left += 1
else:
right -= 1
为什么不需要哈希表？普通两数之和依赖哈希保存历史；本题已经排序，可以利用两端和的单调变化直接排除候选，达到 O(n) 时间和 O(1) 额外空间。
代码—指针—候选空间联动轨迹：[1,2,4,6,8,11], target=10
1class Solution:
2 def twoSum(self, numbers: List[int], target: int) -> List[int]:
3 left, right = 0, len(numbers) - 1
4 while left < right:
5 current_sum = numbers[left] + numbers[right]
6 if current_sum == target:
7 return [left + 1, right + 1]
8 if current_sum < target:
9 left += 1
10 else:
11 right -= 1
逐行播放，观察每次比较如何删除一批候选配对。
完成代码联动后进入批量计数迁移补全正确、查看答案或播放完整轨迹后解锁。
迁移题：LeetCode #2824 统计和小于目标值的数对
先排序。如果 nums[left] + nums[right] < target，那么固定left时，left与 left+1...right 的所有配对都合法，可以一次加入 right-left 个答案；否则令right左移。
本单元形成的算法Skill
在有序数组中，两端元素之和随指针移动具有单调性。当前和偏小时，排除最小左端；当前和偏大时，排除最大右端。双指针的关键不是“从两端开始”，而是每次移动都能证明被排除端点不可能参与答案。
LeetCode #167有序性相向双指针单调排除1-based返回O(n) / O(1)
#125 已完成镜像比较与字符过滤
#283 已完成同向读写指针
#167 当前：单调排除有序数组两端收缩
#15 下一单元固定一个数＋双指针＋去重