对撞双指针框架

套路纲数组与双指针

什么时候想到它(适用信号)

  • 有序数组上找一对数(两数之和、最接近的一对)
  • 求"最宽/最大"的区间型答案(盛水、跨度)
  • 题目暗示从两端开始考虑:最大宽度、最大跨度

一句话核心

两个指针从两端向中间走,每一步都确定性地排除一个不可能更优的候选——是安全的排除,不是碰运气。

通用模板(先背骨架)

js
1function twoPointers(nums) {
2 let left = 0, right = nums.length - 1;
3 while (left < right) {
4 // 根据两端的比较结果,决定移动哪一边(每次只动一个)
5 if (需要更大(nums[left])) {
6 left += 1;
7 } else {
8 right -= 1;
9 }
10 }
11 return 结果;
12}

关键问题清单(做题时按顺序回答,把模板套进去)

  1. 当前两端哪个是"瓶颈"?——移动它才会改变约束(如盛水题:面积由矮板决定)
  2. 为什么移动它是安全的?——能否证明被放弃的那一侧搭档任何位置都不可能更优
  3. 循环条件写 left < right 还是 left <= right?(取决于同一个元素能否用两次)
  4. 每步只移动一个指针——两个都动会不会跳过一个潜在最优解?

常见坑

  • 同时移动两个指针是最常见的错法——会跳过最优解,每步必须只动一个
  • 先想清楚"排除谁、为什么安全",再写代码;凭感觉左右乱移会偶过测试但对错题

← 返回模块首页