双指针利用有序性或连续区间约束减少重复扫描，每次移动都必须有排除候选的证明。

🧭 什么时候考虑这个专题

有序元素对使用相向指针；原地压缩使用快慢指针；固定长度统计用固定窗口；最长或最短连续区间检查可变窗口。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点核心规则常见复杂度
相向指针前提有序性或其他单调关系才能证明移动一侧不会漏解通常 O(n)
左边界不回退最长无重复子串中左边界只能向右移动时间 O(n)
负数与滑动窗口依赖窗口和单调变化的收缩策略通常要求元素非负取决于约束
固定窗口增量更新右端加入新元素时同步移除离开窗口的左端元素时间 O(n)
三数之和去重排序后固定一个元素，并分别跳过固定值与双指针的重复值时间 O(n²)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

  • 相向指针前提： 无序输入不能仅根据当前和决定移动方向
  • 左边界不回退： 旧重复位置在窗口左侧时不能把 left 拉回去
  • 负数与滑动窗口： 存在负数时移除左端可能让窗口和增大
  • 固定窗口增量更新： 窗口长度非法时必须先按契约处理
  • 三数之和去重： 去重必须在记录答案后移动到新的值

C# 实现检查

  1. 方法签名与题目契约一致，不依赖控制台输入输出。
  2. 数值计算检查 int 溢出，必要时先提升为 long。
  3. 集合选择说明平均复杂度、顺序语义和重复值处理。
  4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
  5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

  • 相向指针前提： 不要把“只要使用两个下标就自动得到线性正确算法”当成规则。
  • 左边界不回退： 不要把“发现重复字符时直接令 left 等于旧位置加一”当成规则。
  • 负数与滑动窗口： 不要把“任意连续子数组求和问题都能用同一滑动窗口”当成规则。
  • 固定窗口增量更新： 不要把“每个窗口都应重新遍历求和”当成规则。
  • 三数之和去重： 不要把“使用 HashSet 保存结果即可忽略指针去重”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。