Skip to content

1. 先问:指针分别代表什么 ​

先理解数组与复杂度,并会用 Set、Map 保存已知信息。双指针并不是固定模板,而是用两个位置表达当前的处理状态。

形式两个位置的含义本篇例子
相向指针尚待比较区间的左右端点回文判断
快慢指针已处理结果的写入位置、尚待处理的读取位置移动零
滑动窗口当前连续区间的左右边界无重复字符的最长子串

每次移动之前,都要能说明:被跳过的内容为什么不会影响答案。没有这个依据,两个指针只是两个变量。

本文代码块均可独立运行。输入类型由题目契约保证,示例不承担外部请求的类型校验。

2. 相向双指针:比较两端是否相同 ​

2.1 从反转比较到逐对比较 ​

问题:给定字符串,判断正着读与倒着读是否相同。最直接的方法是创建反转结果再比较;但其实只要检查每一对对称位置,就不需要额外创建反转结果。

本例按 Unicode 代码点逐个比较,保留大小写、标点与空格;空字符串视为回文。它不是“忽略非字母数字字符”的题目版本。

Array.from(text) 把字符串转换成代码点数组,可正确处理单个非基本多文种平面字符,例如 😀。它不做规范化,也不把多个代码点组成的组合字符或表情视为一个字素;处理面向用户的文字时,要先明确所需的字符单位。

2.2 不变量与实现 ​

区间 [left, right] 外的对称位置都已经比较相等。如果当前两端不同,整体就不是回文;相同则各向内移动一步。两指针相遇或交错时,剩余部分不超过一个字符,无需再比较。

js
function isPalindrome(text) {
    const chars = Array.from(text);
    let left = 0;
    let right = chars.length - 1;
    while (left < right) {
        if (chars[left] !== chars[right]) return false;
        left++;
        right--;
    }
    return true;
}

转换和比较的总时间为 O(n),其中 n 为代码点数量。指针本身只占常数空间,但转换数组占 O(n) 辅助空间,不能把这份完整实现写成常数空间。

手推 abca:两端的 a 相等不代表整体成立,内层的 b 与 c 仍须比较。检查空串、单字符、偶数长度、大小写差异以及 😀a😀。

3. 快慢指针:把非零元素稳定写到前面 ​

3.1 朴素方法的成本 ​

问题:把数值数组中的零移到末尾,非零元素的相对顺序保持不变,原地修改输入。本文约定元素为有限数值,0 和 -0 都视为零,不要求保留零的符号;函数返回原数组,便于观察结果。

可以先收集所有非零元素,再补零,但这需要额外数组。也可以遇到零就删除再追加,但中间删除会移动元素,反复进行可能达到二次时间,还容易跳过连续的零。

3.2 已处理前缀的含义 ​

read 负责检查原位置,write 指向下一个非零元素应写入的位置。处理下标 read 之前,[0, write) 保存原输入中已经读过的全部非零元素,且顺序不变。

遇到非零就写入并增加 write;遇到零只增加 read。因为始终有 write <= read,写入不会覆盖尚未读取的元素。扫描完后,所有剩余位置补零。

js
function moveZeroes(nums) {
    let write = 0;
    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== 0) {
            nums[write] = nums[read];
            write++;
        }
    }
    for (let i = write; i < nums.length; i++) nums[i] = 0;
    return nums;
}

先扫描,再补零,两部分总共最多约 2n 次访问,因此时间为 O(n);只有几个下标变量,辅助空间为 O(1)。前面的元素可能已被覆盖,所以不能在算法中途把整个数组当成“原输入”重新读取。

对 [0, 1, 0, 3, 12],扫描后前缀为 [1, 3, 12],write 等于 3;最后将其余位置设为零。不要在看到一个零时立即将它与末尾交换,这可能打乱非零元素顺序。

4. 滑动窗口:找到最长的无重复连续区间 ​

4.1 先发现重复工作 ​

问题:返回字符串中不含重复代码点的最长连续子串长度,空串返回 0。字符单位与回文示例一致;返回的是代码点数量,不是 JavaScript 字符串的 length 所计的代码单元数量。

朴素做法从每个起点向右扫描,用集合检查是否重复;它会反复检查重叠的区间,最坏时间为 O(n²)。例如已知一个区间没有重复,加入新字符后,只需要处理这个新字符引起的冲突。

4.2 为什么左端可以跳过去 ​

扫描右端 right,用 lastSeen 保存每个字符最近出现的位置。若当前字符在位置 previous 出现过,只有当该位置仍在窗口内时,才需要把左端移到 previous + 1。

更新后,[left, right] 没有重复字符,而且是以 right 结尾的最长合法区间。旧窗口已经无重复,新加入的字符最多与自己上一次出现冲突;更早的起点会包含那次冲突,所以可以排除。

js
function lengthOfLongestSubstring(text) {
    const chars = Array.from(text);
    const lastSeen = new Map();
    let left = 0;
    let best = 0;
    for (let right = 0; right < chars.length; right++) {
        const char = chars[right];
        if (lastSeen.has(char)) {
            left = Math.max(left, lastSeen.get(char) + 1);
        }
        lastSeen.set(char, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

按哈希表操作平均常数时间的常用模型,扫描时间为 O(n);代码点数组和位置表总辅助空间为 O(n)。这依赖所采用的成本模型,不是对所有 Map 实现的最坏时间保证。

4.3 反例:左端不能退回去 ​

处理 abba:

右端字符左端更新合法窗口当前最大长度
第一个 a0a1
第一个 b0ab2
第二个 b2b2
最后的 a仍为 2ba2

最后的 a 上次出现在位置 0,已经不在窗口内。如果直接写 left = previous + 1,左端会退回 1,错误地把含重复字符的 bba 当成合法窗口。Math.max 保证左端只前进。

5. 不要把所有连续区间问题都套成滑窗 ​

“连续”只是问题的形状,还需要知道扩张或收缩是否能安全排除候选。

例如求和至少为某个正目标的最短区间,元素全为正数时,右端扩张让和增加,左端收缩让和减少,可以利用这种单调变化。但如果允许负数,这个理由就失效。

对 [1, -1, 3],目标为 3:整个区间满足条件,删除左边的 1 后和为 2;若此时停止收缩,会漏掉继续删除 -1 后的单元素区间 [3]。因此不能把正数版本的“和不足就停止收缩”直接用于负数数组。

无重复字符窗口的依据是重复位置,与区间和的正负无关。学新题时重新写出移动理由,不要仅凭出现“子串”“子数组”就选择滑窗。

6. 验证与闭卷练习 ​

测试直接读取本文代码,运行:

sh
node --test tests/algorithm-window-examples.test.mjs

除了几个典型例子,测试还将小输入穷举结果与简单方法对照,检查空值、重复、顺序、输入修改行为和代码点语义。

  1. 闭卷重写移动零。每次写入前说明为何不会覆盖尚未读取的数;检查全零、无零、连续零和负数。
  2. 手推 abba 与 pwwkew,标记每轮左右边界,再写无重复子串算法。
  3. 将移动零改为删除指定值:返回有效前缀长度,后缀无要求。比较它与移动零的收尾步骤。
  4. 在至少间隔 3 天后重做其中一道,记录是否需要提示。完整安排见算法学习路线。

评论

正在加载评论…