Hot 100 前十二题复盘：双指针、前缀和与单调队列

8 月 27 日晚上刷到了 Hot 100 的前十二题。数量不算多，但已经有几处明显暴露出“看过”和“真正能写出来”之间的距离。三数之和的主体思路还在，容易漏的是命中答案后的左右去重；找到字符串中所有字母异位词几乎忘干净了；和为 K 的子数组能想到前缀和，却必须靠 map.put(0, 1) 才能把边界补齐；滑动窗口最大值最绕的仍然是单调队列，尤其是队首下标什么时候算过期。

这篇不追求把题解写得花哨，主要把当晚卡住的地方重新讲顺。以后再碰到同类题，至少应该能从不变量把代码推出来，而不是只记得几个零散的 API。

15. 三数之和：去重不是最后补的一行

三数之和的常规路线是排序，再固定第一个数，用左右指针寻找另外两个数。排序以后，指针移动有了方向：三数之和小于零就让 L 右移，大于零就让 R 左移。真正容易写漏的部分是去重，而且这里有两层去重。

第一层是固定值 nums[i] 的去重。如果当前值和前一个值相同，那么由它出发找到的三元组一定已经处理过。第二层发生在 sum == 0 时：答案记录下来以后，L 和 R 不能只各走一步，还要先越过与当前值相同的元素。否则同一组三元组会被重复加入。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
}

这里我之前容易把去重理解成一种“优化”，其实它是结果正确性的一部分。固定值去重阻止重复搜索，命中后的左右去重阻止重复答案。两个 while 只放在 sum == 0 的分支里也有原因：未命中时，指针本来就要继续寻找可能的组合；提前大范围跳过虽然有机会写对，却更容易把边界搅乱。

注意L指针是i + 1；

排序的时间复杂度是 O(n log n)，双指针枚举是 O(n²)，所以整体是 O(n²)。额外空间不计算排序内部开销时可以看作 O(1)。

438. 找到字符串中所有字母异位词：固定长度窗口

这道题当晚属于“纯忘了”。重新写一遍后发现，它并没有复杂技巧，关键是先认出窗口长度永远等于 p.length()。右指针每次加入一个字符；窗口过长，就从左边移除一个字符。窗口长度正好时，比较两边的字符频次即可。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;

        int[] windowCount = new int[26];
        int[] targetCount = new int[26];

        for (char c : p.toCharArray()) {
            targetCount[c - 'a']++;
        }

        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            windowCount[s.charAt(right) - 'a']++;

            if (right - left + 1 > p.length()) {
                windowCount[s.charAt(left) - 'a']--;
                left++;
            }

            if (right - left + 1 == p.length()
                    && Arrays.equals(windowCount, targetCount)) {
                res.add(left);
            }
        }
        return res;
    }
}

Arrays.equals 每次会比较 26 个位置，字母表大小固定，因此渐进复杂度仍然是 O(n)。如果字符集更大，或者特别在意常数，可以维护“已有多少种字符的频次恰好匹配”，把每次完整比较变成常数次更新。但在这道题里，26 个整数的比较足够直接，也不容易出错。

这题最值得记住的不是代码，而是识别方式：题目问的是某个定长模式串在长字符串中的所有排列位置。只要顺序不重要、字符数量重要，频次数组就是比排序每个窗口更合适的表达。

560. 和为 K 的子数组：先查再存，别漏掉零前缀

设当前前缀和为 preSum。如果前面出现过一个前缀和 preSum - k，那么从那个位置之后到当前位置的元素之和就是 k：

preSum - oldPreSum = k
oldPreSum = preSum - k

Map 保存的不是“某个前缀和有没有出现”，而是它出现了多少次。同一个 preSum - k 可能对应多个起点，每个起点都能形成一个合法子数组，所以答案要累加频次。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int preSum = 0;
        int count = 0;
        Map<Integer, Integer> frequency = new HashMap<>();

        frequency.put(0, 1);

        for (int num : nums) {
            preSum += num;
            count += frequency.getOrDefault(preSum - k, 0);
            frequency.put(preSum, frequency.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}

map.put(0, 1) 是这道题最容易忘的一行。它表示在读取任何元素之前，存在一次前缀和为零的状态。假设从数组第零位加到当前位置恰好等于 k，这时 preSum - k == 0；如果 Map 中没有预先放入这个零，就会漏掉所有从下标零开始的答案。

另外必须先查询、再记录当前前缀和。如果先把当前 preSum 放进 Map，当 k == 0 时，当前状态可能和自己配对，相当于凭空统计一个长度为零的子数组。时间复杂度是 O(n)，空间复杂度最坏为 O(n)。

239. 滑动窗口最大值：队列里放的是候选人的下标

这道题是本次最需要讲透的一道。暴力做法会在每个窗口里重新寻找最大值，复杂度是 O(nk)。单调队列把“已经不可能成为最大值的元素”提前淘汰，使每个下标最多入队一次、出队一次，最终做到 O(n)。

队列存下标，不直接存数值，因为我们同时需要两种信息：

1. 通过下标判断元素是否已经离开窗口；
2. 通过 nums[index] 比较候选值的大小。

队列从头到尾对应的数值保持单调不增，因此队首始终是当前窗口最大值。每次加入 nums[i]，队列依次做三件事。

第一件事：从队首清理过期下标

当右边界来到 i，长度为 k 的窗口左边界是：

left = i - k + 1

凡是下标小于 left 的元素，都已经落在窗口左侧。因此判断条件是：

queue.peekFirst() < i - k + 1

它也可以写成：

queue.peekFirst() <= i - k

两种写法完全等价。比如 k = 3、i = 4，当前窗口是 [2, 4]，下标 1 以及更小的元素都过期。此时 i - k + 1 == 2，所以“下标小于 2”就是需要删除的范围。

准确的说法应该是“移除已经离开窗口的队首下标”，不是“踢出不在队首的下标”。过期元素之所以一定从队首检查，是因为下标按进入时间自然递增，最老的候选人永远在最前面。

第二件事：从队尾淘汰更小的值

如果队尾对应的值小于当前值，那么它以后不可能成为任何窗口的最大值：当前元素比它更大，而且离开窗口的时间还更晚。这样的队尾应该直接删除，直到队尾不小于当前值。

使用 < 会保留相等元素，使用 <= 会淘汰更早的相等元素，两者都能得到正确答案。<= 可以让队列更短一些；保留 < 则更接近我当晚写下的版本。

第三件事：加入当前下标

旧候选人处理完后，把 i 放到队尾。只有当 i >= k - 1 时，第一个完整窗口才形成，此后每一步都把队首对应值写入答案。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> queue = new ArrayDeque<>();
        int write = 0;

        for (int i = 0; i < nums.length; i++) {
            // 1. 移除已经离开当前窗口的下标
            while (!queue.isEmpty() && queue.peekFirst() < i - k + 1) {
                queue.pollFirst();
            }

            // 2. 淘汰队尾所有比当前值更小的候选人
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }

            // 3. 当前下标成为新的候选人
            queue.offerLast(i);

            if (i >= k - 1) {
                res[write++] = nums[queue.peekFirst()];
            }
        }
        return res;
    }
}

我原来的实现先写进 List<Integer>，最后再通过 Stream 转成 int[]，逻辑没有问题，但这里答案长度从一开始就是确定的：nums.length - k + 1。直接创建数组能省掉装箱、List 扩容和 Stream 转换，代码也更贴近题目要求。

用一个窗口手推队列

拿 nums = [1, 3, -1, -3, 5]、k = 3 简单走一遍：

• 1 入队，队列对应值为 [1]；
• 3 到来，1 比 3 小，从队尾出队，留下 [3]；
• -1 入队，形成第一个窗口，队列是 [3, -1]，最大值是 3；
• -3 入队，队列是 [3, -1, -3]，第二个窗口最大值仍是 3；
• 5 到来前，下标 1 已经落在新窗口 [2, 4] 左边，从队首过期；随后 5 又依次淘汰 -3 和 -1，队列最终只剩 [5]。

队列并不保存窗口的全部内容，只保留“现在或未来仍有机会成为最大值”的下标。理解这一点以后，为什么要从队首删过期元素、从队尾删较小元素，就不再是两段需要死背的模板。

这次真正需要记住的四句话

• 三数之和：固定值要去重，命中答案后左右指针也要去重。
• 字母异位词：窗口长度固定，窗口频次与目标频次相同就记录左边界。
• 和为 K 的子数组：先放入 0 -> 1，每次先查询 preSum - k，再记录当前前缀和。
• 滑动窗口最大值：队首删过期下标，队尾删更小值，最后加入当前下标；窗口完整后答案就在队首。

前十二题刷完以后，最大的感受还是：忘掉一道题不可怕，怕的是只记住最终代码，却说不清每行代码维护了什么。双指针维护有序区间，固定窗口维护字符频次，前缀和 Map 维护历史状态的出现次数，单调队列维护仍然有效的最大值候选人。把这些状态讲清楚，再遇到边界问题时就有地方下手，而不是只能盯着样例碰运气。