对撞双指针框架
套路纲数组与双指针什么时候想到它(适用信号)
- 有序数组上找一对数(两数之和、最接近的一对)
- 求"最宽/最大"的区间型答案(盛水、跨度)
- 题目暗示从两端开始考虑:最大宽度、最大跨度
一句话核心
两个指针从两端向中间走,每一步都确定性地排除一个不可能更优的候选——是安全的排除,不是碰运气。
通用模板(先背骨架)
js1function 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}
关键问题清单(做题时按顺序回答,把模板套进去)
- 当前两端哪个是"瓶颈"?——移动它才会改变约束(如盛水题:面积由矮板决定)
- 为什么移动它是安全的?——能否证明被放弃的那一侧搭档任何位置都不可能更优
- 循环条件写 left < right 还是 left <= right?(取决于同一个元素能否用两次)
- 每步只移动一个指针——两个都动会不会跳过一个潜在最优解?
常见坑
- 同时移动两个指针是最常见的错法——会跳过最优解,每步必须只动一个
- 先想清楚"排除谁、为什么安全",再写代码;凭感觉左右乱移会偶过测试但对错题