2025年12月6日

02 Two Pointers

1. Valid Palindrome

题目：给一个字符串，判断它是否是回文串。只考虑字母和数字字符，忽略大小写和其他所有符号（空格、标点等）。

思路：左右两个指针分别从字符串两端往中间移动，跳过非字母数字字符，比较字符（忽略大小写）是否相同，不同则不是回文。

要点：

需要一边移动指针一边判断当前字符是否是字母/数字（isalnum 之类），不是就跳过，不能先把字符串"清洗"成新字符串再比——虽然清洗后再判断也对，但那样是 O(n) 额外空间，双指针原地做可以省这个空间。
比较字符时注意统一大小写（lower()），容易漏掉这一步导致大小写不同的字母误判为不相等。
边界情况：空字符串、全是符号的字符串（跳过所有字符后指针相遇），这些默认是回文，容易忘记测试。

题目：给一个已按升序排序的数组，找出两个数相加等于 target 的下标（下标从 1 开始，假设有且仅有一个解）。

思路：左指针指向开头，右指针指向结尾。如果两数之和大于 target，右指针左移（减小和）；如果小于 target，左指针右移（增大和）；相等则找到答案。

要点：

这题和普通 Two Sum 的区别就是数组有序，有序性是能用双指针的前提——如果数组无序，双指针的"和变大变小"逻辑就不成立了，只能退回哈希表方法。
反直觉点（容易和 Two Sum 搞混）：这题不需要哈希表，很多人惯性思维直接套用 Two Sum 的哈希解法，其实是杀鸡用牛刀，双指针在这里是 O(n) 时间 O(1) 空间，比哈希表更优。
记住返回下标一般要求从 1 开始（题目原版设定），这是个容易漏看的细节。
这题是双指针"夹逼"（收缩边界）模式的入门标准模板，后面 3Sum、Container With Most Water 都是这个模板的变形。

题目：给一个数组，找出所有和为 0 的三元组（不能重复）。

思路：

要点：

排序是前提：不排序既没法用双指针夹逼，也没法方便地跳过重复元素。这是这题和 Two Sum 系列最大的区别——多了一步排序，O(n log n)，但整体复杂度仍由后面的双指针部分决定，是 O(n²)。
去重逻辑是这题最容易写错的地方，需要在两个地方去重：
- 外层固定 i 时，如果 nums[i] == nums[i-1]，跳过（避免固定同一个数两次产生重复三元组）。
- 内层双指针找到一个解之后，左指针要跳过所有和当前值相同的数，右指针同理，再继续收缩，否则会把同一组数字重复计入结果。
反直觉点：直觉上可能想用哈希表把 3Sum 转化为对每个数做一次 Two Sum（这样确实可行，复杂度也是 O(n²)），但去重逻辑会更麻烦，双指针配合排序是更干净的标准解法。
小优化：固定第一个数 nums[i] 时，如果 nums[i] > 0，后面不可能再凑出和为 0（因为数组已排序，后面都是正数），可以直接跳出循环。

题目：给一个数组，height[i] 表示第 i 条竖线的高度，两条竖线和 x 轴构成一个容器，找出能装最多水的两条线，返回最大容积（面积 = 两线间距 × 较矮那条线的高度）。

思路：左右指针分别指向数组两端，计算当前面积，然后移动较矮的那根指针向中间靠拢，不断更新最大面积。

要点：

核心反直觉点（这题的灵魂）：为什么每次移动"较矮"的指针，而不是较高的？
- 因为面积由较矮的线决定，如果移动较高的那根，宽度变小，而高度上限还是被那根矮线卡住（甚至更矮），面积只可能变小或不变，绝不会变大。
- 而移动较矮的那根，虽然宽度也变小，但至少有可能遇到一个更高的线，从而让面积有变大的可能性。
- 这个"移动矮的指针"的正确性证明是很多人一开始想不通、需要专门理解并记住的点，不是靠直觉能一眼看穿的。
暴力解法是双重循环枚举所有两条线的组合，O(n²)；双指针做法一次遍历就能把所有"次优组合"排除掉，是 O(n)，属于"排除法"思路（每一步都能确定性地排除掉一部分不可能是最优解的组合），而不是单纯的"夹逼找目标值"。

题目：给一个数组表示地形高度图，计算下雨后能接住多少单位的雨水。

思路（进阶双指针解法）：

每个位置 i 能接的水量 = min(左边最高的墙, 右边最高的墙) - height[i]（如果是负数则为 0）。
用两个指针 left 和 right 从两端往中间移动，同时维护 leftMax 和 rightMax 两个变量记录当前各自这一侧遍历过的最大高度。
每一步比较 leftMax 和 rightMax：
- 如果 leftMax < rightMax，说明左边这一侧的水位是被 leftMax 卡住的（右边一定够高，不会是短板），可以直接结算 left 位置的接水量并右移 left。
- 反之同理，结算 right 位置并左移 right。

要点：

朴素解法：对每个位置分别向左向右找最大值，O(n²)；或者预处理两个数组 leftMax[] 和 rightMax[]，O(n) 时间但 O(n) 额外空间——这是大多数人能想到的"次优解"，是很好的过渡方案，面试时可以先说这个再优化。
双指针 O(1) 空间解法的核心反直觉点：
- 为什么只要比较 leftMax 和 rightMax 的大小关系，就能确定"较小一侧"当前指针位置的接水量是准确的，而不需要知道对面还没走到的真实最大值？
- 关键在于：如果 leftMax < rightMax，那么无论右边还没探索到的部分有多高，右边的最大值一定 ≥ rightMax > leftMax，所以此时 left 位置的接水量的瓶颈一定是 leftMax，跟右边具体多高无关，可以放心结算。
- 这一步"不需要精确知道对侧最大值，只需要知道大小关系"的逻辑跳跃，是这题里最难独立想出来、最需要专门记住的部分。
这题和 Container With Most Water 都用双指针从两端夹逼，但目的完全不同：Container 是找最大面积（贪心排除法），Trapping Rain Water 是精确计算每个位置的接水量（需要维护状态变量 leftMax/rightMax），不要把两题的双指针移动逻辑弄混。

套路	出现在哪些题
有序数组下，双指针替代哈希表做夹逼查找	Two Sum II
排序 + 固定一个数 + 双指针夹逼，降维处理多数之和	3Sum
移动"较小/较矮"的一侧指针来做贪心排除	Container With Most Water
维护左右两侧的状态最大值，用大小关系代替精确值来结算	Trapping Rain Water
从两端往中间收缩，不走回头路，保证整体 O(n)	本专题几乎所有题

一个通用判断标准：看到"排序数组"或者问题能转化为"排序数组"的场景，且需要找到满足某个和/差/乘积关系的一对（或几个）元素时，第一反应可以想双指针，往往能把哈希表方法的空间开销省掉。