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 ≤ 1000
  • numbers 按非递减顺序排列；
  • 恰好存在一个答案，且同一元素不能使用两次。

示例

numbers = [2,7,11,15], target = 9
输出：[1,2]
numbers = [2,3,4], target = 6
输出：[1,3]
numbers = [-1,0], target = -1
输出：[1,2]

索引提醒

Python列表内部仍用 0-based 索引；只有返回答案时才统一加 1。

1. 体验组合枚举
2. 发现单调方向
3. 证明安全排除
4. 代码联动
5. 批量计数迁移
先连接上一单元：指针名称相似，但角色已经改变Unit 02 → Unit 03
#283：同向读写指针

fast 读取每个元素，slow 维护正确前缀。核心不变量是“左侧已经整理完成”。

→
#167：相向排除指针

left 与 right 都在读取区间端点。核心不变量是“答案仍在未排除区间内”。

真正迁移的不是 left、right、fast、slow 这些名字，而是：每个指针维护什么边界，以及为什么一次移动可以安全地缩小问题。
演示：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 统计和小于目标值的数对

先完整理解迁移题要求统计什么、返回什么，再讨论它与 #167 的联系。完成原题阅读检查后，才进入“排序＋相向双指针＋批量计数”的结构迁移。

1. 认识 #2824 原题
2. 对照精确查找与批量计数
3. 映射四个变化槽位
4. 拼装并运行批量证明

先读题：统计和小于目标值的数对

这一阶段只确认统计对象、下标条件、严格不等式和返回值，不提前套用 #167 的算法。

LeetCode #2824 · Easy
题目要求

给定一个下标从 0 开始的整数数组 nums 和整数 target，统计满足 0 ≤ i < j < len(nums) 且 nums[i] + nums[j] < target 的下标对 (i,j) 数量，并返回这个数量。

class Solution: def countPairs(self, nums: List[int], target: int) -> int: # 返回满足条件的下标对数量
约束与提醒
  • 1 ≤ len(nums) ≤ 50
  • -50 ≤ nums[i], target ≤ 50
  • 输入数组不保证有序。
  • 统计的是不同下标对；相同数值出现在不同下标时仍可分别计数。
原题示例
输入：nums = [-1,1,2,3,1], target = 2 输出：3 解释：合法下标对为 (0,1)、(0,2)、(0,4)。
输入：nums = [-6,2,5,-2,-7,-1,3], target = -2 输出：10
统计下标对数量 必须满足 i < j 严格小于 target 不是寻找一个答案 返回整数计数

读题检查 A｜函数最终应该返回什么？

读题检查 B｜示例 [-1,1,2,3,1], target=2 为什么返回3？

先完成两道读题检查。理解“返回所有合法下标对的数量，而不是返回某一个数对”后，才进入算法结构对照。

已经掌握：#167 两数之和 II

有序性：题目已经保证 目标：找到一个 sum == target 的数对 命中后：立即返回两个位置 排除规则：偏小 left++，偏大 right--

准备迁移：#2824 统计合法数对

有序性：需要自己建立 目标：统计所有 sum < target 的数对 命中后：不能立即返回，要累计一批答案 排除规则：等待从单调性重新推出
保持不变左右指针夹住未处理区间；每轮只比较两端之和；指针只向中间移动。
需要改变先排序；把“找到一个解”改成“确认一整批解”；最终返回累计数量。
迁移的核心桥梁 若 nums[left] + nums[right] < target，由于数组有序，那么固定 left 后，和更小的 left+1...right-1 配对也全部合法。因此不是只发现 1 个答案，而是一次发现 right-left 个答案。

先判断迁移幅度：下面哪句话最准确？

槽位 A｜#167 的有序性由题目提供，新题应该怎样补回？

槽位 B｜需要新增什么状态来保存累计结果？

槽位 C｜当两端和小于 target 时，怎样一次接收整批合法配对？

固定 left 后，合法右端是 left+1...right，数量正好为 right-left。这批配对计数完后，left 才能安全右移。

槽位 D｜所有区间处理完后返回什么？

从 #167 保留下来的控制骨架left, right = 0, len(nums) - 1
while left < right:
    current_sum = nums[left] + nums[right]
    if ...:
        ...
    else:
        right -= 1
本题真正新增的证明当前最大右端都能与 left 组成合法数对时，更小的所有右端也必然合法，所以可以批量增加 right-left。
认知压缩：不是把 #167 的 return 换成循环计数，而是把“相等即命中”改造成“阈值成立即整批接收”。

#167：寻找一个精确配对

# numbers 已经有序
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

#2824：统计所有阈值内配对

nums.sort()
left, right = 0, len(nums) - 1
answer = 0
while left < right:
    current_sum = nums[left] + nums[right]
    if current_sum < target:
        answer += right - left
        left += 1
    else:
        right -= 1
return answer
准备运行
可选：脱离槽位后独立重写一次

这一步不影响完成本单元。建议先完整运行批量计数证明，再凭记忆重写。

本单元形成的算法Skill

在有序数组中，两端元素之和随指针移动具有单调性。当前和偏小时，排除最小左端；当前和偏大时，排除最大右端。双指针的关键不是“从两端开始”，而是每次移动都能证明被排除端点不可能参与答案。

LeetCode #167有序性相向双指针单调排除1-based返回O(n) / O(1)
#125 已完成镜像比较与字符过滤
#283 已完成同向读写指针
#167 当前：单调排除有序数组两端收缩
#15 下一单元固定一个数＋双指针＋去重