双指针与滑动窗口 · HTML
数学 / 逻辑形态
维护候选对 (l,r) 且 l<r。依据 f(a[l],a[r]) 与目标的单调比较，移动 l 或 r；被越过端点不可能参与未检查的更优/可行解。
识别信号
- 输入有序，目标涉及一对元素。
- 题意是回文对称检查或两端比较。
- 端点组合过大/过小时，移动某一端有确定方向。
- 暴力枚举 O(n²) 对，但排序后可线性夹逼。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 无序配对且需原索引 | 哈希往往 O(n) 且免排序；相向指针需先处理排序与索引映射。 |
| 连续子数组约束 | 若维护整个区间的频次/和，通常是可变滑窗，不是只看端点对。 |
核心不变量
所有尚未排除的候选对端点都位于 [l,r]；每次移动的端点已被单调性证明无法与区间内另一点形成所需解。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 左指针 l、右指针 r、端点值及可选的当前最佳答案。 |
| Transition | 比较端点组合；命中则记录/返回，组合偏小移动 l，偏大移动 r，具体方向由单调性证明。 |
| Frontier / order | 二维候选对矩阵中尚未排除的阶梯边界，被两个一维指针压缩表示。 |
Python 骨架
def pair_with_sum(sorted_values, target):
left, right = 0, len(sorted_values) - 1
while left < right:
total = sorted_values[left] + sorted_values[right]
if total == target:
return left, right
if total < target:
left += 1
else:
right -= 1
return None
正确性思路
- 若当前和小于目标，固定最小值与任何不超过当前右端的数相加都不会更大，故可排除 left。
- 若当前和大于目标，对称地可排除 right。
- 每步保留所有仍可能命中的对并严格缩小区间；命中正确，耗尽则无解。
复杂度
| Time | Space | Parameters |
|---|
| O(n)（若需先排序则 O(n log n)） | O(1)（排序副本/索引映射另计） | n 为元素数；两个指针各最多移动 n 次。 |
边界条件
- 少于两个元素无候选对。
- 重复值可能构成合法对，必须用不同索引。
- 需要所有配对时命中后要跳过重复值或按要求计数。
- 数值溢出语言中端点求和需更宽类型。
错误模式
| Pattern | Why it fails / fix |
|---|
| 没有单调排除证明 | 仅因“看起来该移动”就移动指针，可能漏解。 |
| while left<=right | 会把同一元素与自己配对；普通两元素题用 left<right。 |
| 排序后丢原索引 | 若输出原位置，应排序 (value,index) 对。 |
选择与排除规则
- 有序数组的双元素关系：先试相向夹逼。
- 必须保持原序且只求存在：哈希可能更直接。
- 要维护区间整体统计：转滑动窗口。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 返回端点值 1 与 9。 |
| Setup | 有序值 [1,4,6,9,13]，目标和 10。 |
| Trace | 1+13 太大，右移到 9；1+9 命中。 |
Recall prompts
我的补充