3. 数组与字符串高频题
数组和字符串是算法面试中出现频率最高的两类数据结构。它们的题目看似千变万化，但真正落到解题层面，绝大多数都可以归入六类模板：双指针、原地修改、前缀和、差分数组、字符串匹配、回文与子串。本章不追求覆盖所有变体，而是把这六类模板的适用条件、推导过程和代码骨架讲清楚，让你在面试中能快速判断“这题该用哪个模板”。
一、双指针：先判断指针移动方向是否单调
双指针的核心不是“用两个变量”，而是两个指针的移动方向具有单调性，从而把 O(n²) 的暴力枚举压缩到 O(n)。常见的三种形态是：对撞指针（左右向中间靠）、快慢指针（同向不同速）、滑动窗口（同向但窗口边界各自只前进）。
以“有序数组两数之和”为例，给定 nums = [2, 7, 11, 15]，target = 9。设左指针 l = 0，右指针 r = 3。计算 nums[l] + nums[r] = 2 + 15 = 17 > 9，因为数组升序，右指针左移只会让和更小，所以 r--；此时 2 + 11 = 13 > 9，继续 r--；2 + 7 = 9，命中。整个过程中每个指针最多移动 n 次，时间复杂度 O(n)。
滑动窗口则要额外维护窗口内的状态。以“无重复字符的最长子串”为例，输入 s = "abcabcbb"。用 right 扩张窗口，用哈希表记录字符最近出现的位置；当 s[right] 已存在且位置 last >= left 时，把 left 跳到 last + 1。窗口右移到第二个 a（下标 3）时，last = 0，left 从 0 跳到 1，窗口变为 "bca"，长度 3。继续右移，最终最长长度为 3。这里的关键判断是：窗口收缩的条件必须能由右指针扩张触发，且左指针不回退。
二、原地修改：读写指针分离
原地修改类题目通常要求 O(1) 额外空间，典型代表是“移除元素”“删除有序数组中的重复项”“移动零”。统一模板是读写指针分离：read 遍历整个数组，write 指向下一个待写入位置，只有满足保留条件的元素才写入 nums[write++]。
以“删除有序数组中的重复项”为例，输入 nums = [1, 1, 2, 2, 3]。初始化 write = 1，从 read = 1 开始遍历：nums[1] = 1 与 nums[write-1] = 1 相等，跳过；nums[2] = 2 不等，写入 nums[1] = 2，write = 2；nums[3] = 2 相等，跳过；nums[4] = 3 不等，写入 nums[2] = 3，write = 3。最终返回长度 3，数组前三位为 [1, 2, 3]。注意：题目只要求返回新长度并保证前 k 位正确，不要求清理尾部。
“移动零”是同一模板的变体：保留条件从“不等于前一个”变成“不等于 0”，写入后把剩余位置补 0 即可。判断是否该用这个模板，看两个信号：题目明确要求原地、且元素的相对顺序需要保持。
三、前缀和与差分数组：一对互逆操作
前缀和解决“多次区间求和”，差分数组解决“多次区间加减”。两者互为逆运算，理解其中一个，另一个自然成立。
前缀和定义 pre[i] = nums[0] + ... + nums[i-1]，则区间 [l, r] 的和为 pre[r+1] - pre[l]。以 nums = [3, 1, 4, 1, 5] 为例，pre = [0, 3, 4, 8, 9, 14]。求下标 1 到 3 的和：pre[4] - pre[1] = 9 - 3 = 6，与 1 + 4 + 1 = 6 一致。前缀和常与哈希表结合，用于“和为 k 的子数组”：遍历时把 pre[i] 存入哈希表，查询 pre[i] - k 是否出现过，出现次数即为以 i 结尾的合法子数组数量。
差分数组是前缀和的逆操作。若要对 [l, r] 区间统一加 v，只需 diff[l] += v、diff[r+1] -= v，最后对 diff 求前缀和即可还原。以“航班预订统计”为例，bookings = [[1,2,10],[2,3,20],[2,5,25]]，n = 5。按 1-based 下标处理：第一条 diff[1] += 10, diff[3] -= 10；第二条 diff[2] += 20, diff[4] -= 20；第三条 diff[2] += 25, diff[6] -= 25（越界忽略）。对 diff 求前缀和得到 [10, 55, 45, 25, 25]，即每个航班的预订总数。差分数组的价值在于把每次区间修改从 O(n) 降到 O(1)。
四、字符串匹配：先想清楚“模式”的规模
字符串匹配的模板选择取决于模式串长度和是否需要多次匹配。如果只是单次匹配且模式串很短，直接调用语言内置的 indexOf 或 find 即可；如果模式串较长或需要多次匹配，应使用 KMP 或 Rabin-Karp。
KMP 的核心是 next 数组（也叫前缀函数），next[i] 表示 pattern[0..i] 的最长相等前后缀长度。以 pattern = "ababaca" 为例，next = [0, 0, 1, 2, 3, 0, 1]。匹配时若 text[j] != pattern[i]，令 i = next[i-1] 而不是回退 j，从而保证主串指针不回退，时间复杂度 O(n + m)。
Rabin-Karp 则用滚动哈希把每个长度为 m 的子串映射为整数，比较哈希值。它的优势是易于扩展到“多个模式串”或“二维匹配”，代价是需要处理哈希冲突。面试中如果面试官没有明确要求手写 KMP，可以先说明思路并给出内置函数的写法，再补充 KMP 的适用场景。
五、回文与子串：中心扩展与动态规划的取舍
回文类问题的两个主力模板是中心扩展和动态规划。中心扩展适合“求最长回文子串”，枚举 2n-1 个中心（n 个字符中心 + n-1 个间隙中心），向两边扩展。以 s = "babad" 为例，以 s[1] = 'a' 为中心扩展得到 "bab"，以 s[2] = 'b' 为中心扩展得到 "aba"，两者长度都是 3，返回任意一个即可。中心扩展的时间复杂度 O(n²)，空间 O(1)。
动态规划适合“回文子串计数”或“分割回文串”。定义 dp[i][j] 表示 s[i..j] 是否为回文，转移为 s[i] == s[j] && (j - i < 2 || dp[i+1][j-1])。注意遍历顺序必须按子串长度递增，否则 dp[i+1][j-1] 尚未计算。以 s = "aaa" 为例，长度为 1 的三个子串都是回文，长度为 2 的三个子串也都是回文，长度为 3 的 "aaa" 也是回文，总计 6 个回文子串。
六、模板选择速查与实战建议
把上面的判断浓缩成一张决策表，面试时可以先在草稿纸上快速定位：
| 题目特征 | 首选模板 | 关键判断 |
|---|---|---|
| 有序数组找配对 / 去重 | 对撞双指针 | 指针移动是否单调 |
| 最长/最短满足条件的连续子串 | 滑动窗口 | 窗口收缩条件是否由右指针触发 |
| 原地删除 / 移动元素 | 读写指针 | 保留条件与相对顺序 |
| 多次区间求和 | 前缀和 + 哈希 | 是否需要统计出现次数 |
| 多次区间加减 | 差分数组 | 是否只需最终结果 |
| 单次短模式匹配 | 内置函数 | 模式串长度与匹配次数 |
| 长模式 / 多模式匹配 | KMP / Rabin-Karp | 是否需要避免主串回退 |
| 最长回文子串 | 中心扩展 | 2n-1 个中心 |
| 回文子串计数 / 分割 | 区间 DP | 按长度递增遍历 |
最后给一个可执行的练习建议：拿 LeetCode 上对应标签的题目，每类模板先做 3 道，做完后不要立刻看下一题，而是合上代码，用一句话写出“这题为什么用这个模板、指针/状态如何变化、边界条件是什么”。例如做完“长度最小的子数组”后，你应该能写出：窗口右扩累加和，当和 ≥ target 时记录长度并左移收缩，左指针不回退，时间复杂度 O(n)。能写出这句话，才算真正掌握了模板，而不是背下了代码。
面试中还有一个常被忽略的细节：先和面试官确认输入约束。数组是否有序、是否允许修改原数组、字符串字符集是 ASCII 还是 Unicode、是否区分大小写，这些都会直接改变模板选择。例如“是否允许修改原数组”决定了你能不能排序后用对撞指针；“字符集大小”决定了滑动窗口用数组还是哈希表。把这些问清楚，再动手写代码，比写完再改要高效得多。