Go back

LeetCode Hot 100——子串篇（前缀和与单调队列）

LeetCode Hot 100 · 子串篇

子串类题目是手撕面试的「重灾区」，不是因为它难到不可解，而是因为它套路感强、一变形就容易卡壳。Hot 100 里「子串」分类只有 3 道，但这 3 道恰好覆盖了三个最重要的子串套路：

  1. 前缀和 + 哈希——把「区间求和」变成「两个前缀和之差」；
  2. 单调队列——在滑动窗口里 O(1) 取最值；
  3. 可变长滑动窗口（双指针）——right 扩张、left 收缩，动态维护窗口合法性。

这三招学会了，字节、腾讯、阿里 80% 的子串/子数组题都能找到落点。下面逐题拆解，每个都从暴力到最优、从代码到复杂度一步步推。

#560 和为 K 的子数组

题意

给定整数数组 nums 和一个整数 k，统计和为 k 的连续子数组的个数。

输入：nums = [1,1,1], k = 2
输出：2          // 子数组 [1,1]（下标 0~1）和 [1,1]（下标 1~2）

注意两点：一是子数组必须连续；二是数组里可能有负数，所以不能用「窗口和单调」来做收缩（前缀和不是单调的），这也是很多人一上来就踩的坑。

难点与易错点

  1. 负数是最大的坑：一旦 nums 里有负数，前缀和就不再单调递增，滑动窗口「右移扩张、左移收缩」的套路直接失效（你不知道该不该收缩，收缩可能丢掉一个负数后反而和变大）。所以这题必须用前缀和 + 哈希，而不是窗口。
  2. map.put(0, 1) 的初始化：它对应「从数组起点开始的子数组」——当 prefixSum == k 时，需要查 prefixSum - k == 0 是否出现过，若不预置 0 -> 1，这类子数组会被漏算。这是最容易漏掉的一行。
  3. 「先查后存」的顺序：必须先累加答案、再把当前前缀和放入 map。如果先存后查，会把 prefixSum - k == prefixSum（即 k == 0）这种「空区间」误算进去，导致空子数组被计数。
  4. 计数而非判存在：map 里存的是「前缀和出现的次数」，不是「是否出现过」。因为可能有多个位置前缀和相同，每个都能和当前位置组成一个合法子数组，漏掉次数就会少算。

解法一：暴力 / 直观

最朴素的想法：枚举所有子数组 [i, j]，累加判断和是否等于 k。枚举起点 i，再向右扩展终点 j，边扩展边累加，即可省去最内层循环，得到 O(n²) 版本：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        // 枚举子数组的起点
        for (int i = 0; i < n; i++) {
            int sum = 0;
            // 从起点 i 向右扩展终点，边扩展边累加
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

复杂度：外层循环 n 次，内层最多 n 次，所以是 O(n²)；只用了一个 sum 变量，空间 O(1)。

瓶颈在哪：每个子数组的和都被从头重新累加，[i, j] 和 [i, j+1] 之间只差一个元素，却要重算一遍，存在大量重复求和。当 n 到 10⁴~10⁵ 量级时，O(n²) 直接超时。

更暴力的三重循环 O(n³)（枚举起点 + 枚举终点 + 内部再求和）只是把「扩展累加」又换成了「每次求和」，思路一致但更慢，手撕时提一句 O(n²) 优化版即可。

解法二：优化 / 最优（前缀和 + 哈希）

题目本质：把「区间求和」转化为「两个前缀和之差」。定义 prefixSum[i] 为前 i 个元素之和，那么子数组 (i, j] 的和 = prefixSum[j] - prefixSum[i]。要满足和为 k，即：

prefixSum[j] - prefixSum[i] == k  ⟺  prefixSum[i] == prefixSum[j] - k

于是问题变成：遍历到 j 时，找前面有多少个位置 i 的前缀和等于 prefixSum[j] - k。用一个 HashMap 记录「每个前缀和出现了多少次」，O(1) 查询。

现实类比：银行流水统计。prefix 记录累计净收入，要找出某段时间净收入恰好为 k 的时段，只需查「当前累计值 - k」这个值在账本里出现过几次——提前把每个累计值出现的次数记在账本（HashMap）里即可。

容器选择：HashMap<Integer, Integer>——需要 O(1) 查询「某前缀和出现了多少次」，key 是前缀和、value 是出现次数；put(0, 1) 用于处理从下标 0 开始的子数组。

三步主线：

  1. 初始化 map.put(0, 1)，prefixSum = 0；
  2. 遍历数组累加 prefixSum，查询 prefixSum - k 的出现次数并累加到答案；
  3. 将当前 prefixSum 计数 +1 存入 map，继续遍历。
class Solution {
    public int subarraySum(int[] nums, int k) {
        // 记录每个前缀和出现的次数
        Map<Integer, Integer> prefixCount = new HashMap<>();

        // 初始化：前缀和为 0 出现 1 次
        // 作用：处理从下标 0 开始的子数组（此时 prefixSum - k = 0）
        prefixCount.put(0, 1);

        int prefixSum = 0; // 当前累计前缀和
        int result = 0;    // 满足条件的子数组数量

        for (int num : nums) {
            prefixSum += num; // 更新前缀和

            // 查找是否存在之前某位置的前缀和 = prefixSum - k
            // 若存在，则该位置到当前位置的区间和恰为 k
            result += prefixCount.getOrDefault(prefixSum - k, 0);

            // 将当前前缀和加入计数表，Java 8 merge 简化累加
            prefixCount.merge(prefixSum, 1, Integer::sum);
        }

        return result;
    }
}

> **💭 思考**：为什么这题必须用「前缀和 + 哈希」而不是滑动窗口？一步步想——最直观是枚举所有子数组求和，O(n²) 的瓶颈在于每个子数组的和都被从头重新累加。看到「连续子数组的和」这种区间求和，第一反应就该是前缀和，把 `区间和 = prefixSum[j] - prefixSum[i]` 拆成两个单点值之差，一次 O(1) 就拿到任意区间和。但光有前缀和还不够：要找 `prefixSum[i] == prefixSum[j] - k`，本质是「前面有多少个值为 X 的东西」，这正是哈希表计数的信号（数值 → 次数，O(1) 查询）。而数组里可能有负数、前缀和不单调，滑动窗口「该不该收缩」根本判断不了，所以窗口路线此路不通，只剩前缀和 + 哈希这一条。

复杂度逐步推导：

多解法对比

解法时间复杂度空间复杂度适用场景
暴力 O(n³)O(n³)O(1)仅用于理解题意，必超时
前缀和暴力O(n²)O(1)数据量小（n ≤ 10³）时可过
前缀和 + 哈希O(n)O(n)本题最优，处理负数、大数据量

本题约束下（n 可达 2×10⁴，且元素含负数），只有前缀和 + 哈希能在线性时间内同时解决「求区间和」与「负数导致前缀和不单调」两大难点，因此选它作为最优解。空间 O(n) 的代价在「必须记录每个前缀和出现次数」的前提下是不可避免的。

CodeTop 变体

#239 滑动窗口最大值

题意

给定整数数组 nums 和窗口大小 k，返回每个滑动窗口中的最大值。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
// 窗口依次为 [1,3,-1]、[3,-1,-3]、[-1,-3,5]、[-3,5,3]、[5,3,6]、[3,6,7]

窗口从左向右一格一格滑动，每滑一格都要返回当前窗口内的最大值。

难点与易错点

  1. 「次大值」会变成「最大值」：窗口滑动时，最大值可能刚出窗口，此时答案变成了窗口内第二大的元素。所以不能只记一个当前最大值，必须维护一个「候选最大值」的队列，让次大、第三大都有序保留。
  2. 淘汰时机要分清：新元素入队时，要淘汰队尾所有比它小的元素（这些元素永远不可能再成为最大值）；窗口左边界右移时，要淘汰「已经滑出窗口」的队头。「淘汰更小的」和「淘汰过期的」是两件事，写混了就错。
  3. 过期的判断方式：如果队列里存的是元素值，判断队头是否过期要看「队头是否等于刚离开窗口的值」（用 == 与 int 比较会自动拆箱，安全）；如果存的是下标，则直接看「队头下标是否小于窗口左边界」。存下标是更通用的写法，能天然规避重复值带来的歧义。
  4. 窗口未满时不记录答案：前 k-1 个窗口还没装满，此时不能输出最大值，否则数组长度对不上。代码里用「左边界 i >= 0」来精确控制。

解法一：暴力 / 直观

枚举每个窗口的起点，扫描窗口内 k 个元素取最大值：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // 枚举每个窗口的起点
        for (int i = 0; i <= n - k; i++) {
            int max = Integer.MIN_VALUE;
            // 扫描窗口内 k 个元素求最大值
            for (int j = i; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            result[i] = max;
        }
        return result;
    }
}

复杂度：共有 n - k + 1 个窗口，每个窗口扫描 k 个元素，所以是 (n - k + 1) × k，近似 O(nk)；空间 O(1)（结果数组不计入）。

瓶颈在哪：相邻两个窗口之间有 k - 1 个元素是重叠的，暴力法却每个窗口都从头比一遍，重叠部分被重复比较，白白浪费。当 k 接近 n 时退化成 O(n²)。

解法二：优化 / 最优（单调递减双端队列）

题目本质：用一个单调递减的双端队列（单调队列）维护窗口内的候选最大值。队列从队头到队尾单调递减，因此队头永远是当前窗口的最大值；新元素入队时，从队尾把所有比它小的元素都踢掉（这些元素在窗口内已被新元素「遮蔽」，永远不可能再成为最大值）。

现实类比：机场安检等候室。只保留「真正有竞争力」的候选最大值——进来一个更大的值，前面那些较小的、永远不可能成为最大值的就被淘汰出队；队头站着的就是当前窗口的答案。

容器选择：Deque<Integer>（存元素值）。因为需要双端操作（队尾加入/删除、队头读取/过期删除），而 ArrayDeque 比 LinkedList 更高效（底层是环形数组，无需为每个节点分配内存）。

三步主线：

  1. i（窗口左边界）和 j（右边界）同步移动（i 从 1 - k 起始，保证 i >= 0 时窗口恰好装满），j 扩张前先删除过期的队头（若队头等于刚离开窗口的 nums[i-1]）；
  2. 维持单调递减：将队尾所有小于 nums[j] 的元素出队，再把 nums[j] 入队尾；
  3. 当窗口已满（i >= 0），记录队头 deque.peekFirst() 为当前窗口最大值。
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // 单调递减双端队列，存储元素值（非下标）
        Deque<Integer> deque = new ArrayDeque<>();

        // i 是窗口左边界（从 1-k 开始，确保 i>=0 时窗口已满）
        // j 是窗口右边界
        for (int i = 1 - k, j = 0; j < n; i++, j++) {
            // 左边界右移时，删除刚离开窗口的元素（即 nums[i-1]）
            // 若队头正好是该值才删除（更小的值早已被弹出）
            if (i > 0 && deque.peekFirst() == nums[i - 1]) {
                deque.removeFirst();
            }

            // 维护单调递减：将队尾所有小于新元素的值出队
            // 这些值在当前窗口内已被新元素"遮蔽"，永远不可能成为最大值
            while (!deque.isEmpty() && nums[j] > deque.peekLast()) {
                deque.removeLast();
            }

            // 将新元素入队尾
            deque.offerLast(nums[j]);

            // 窗口已满，记录当前最大值（队头）
            if (i >= 0) {
                result[i] = deque.peekFirst();
            }
        }

        return result;
    }
}

💭 思考：为什么窗口最大值要用「单调递减队列」而不是只记一个最大值？一步步想——暴力每个窗口从头比一遍，瓶颈是相邻窗口有 k-1 个重叠元素被重复比较。于是想「能不能把上一轮的比较结果复用起来」：维护一个「候选最大值」序列。关键洞察是，新元素入队时，队尾所有比它小的元素已经永远不可能再成为最大值（它们既比新元素小、又比新元素先过期），可以直接淘汰；而队头如果滑出了窗口也要淘汰——「淘汰更小的」和「淘汰过期的」是两件事。这样队列从队头到队尾单调递减，队头天然就是当前窗口最大值，取最值从 O(k) 降到 O(1)。

进阶提示：更通用、更能规避重复值歧义的写法是队列里存下标。入队时 nums[队尾] < nums[j] 就弹出队尾；过期判断改为 deque.peekFirst() < i（即队头下标已小于窗口左边界）。面试官若追问「数组有重复值会不会错」，存下标版本是标准答案。

复杂度逐步推导：

多解法对比

解法时间复杂度空间复杂度适用场景
暴力扫描O(nk)O(1)k 很小时可用，k 大时超时
单调队列O(n)O(k)本题最优，任何 k 均线性

本题约束下（n 可达 10⁵，k 可达 n），暴力法的 O(nk) 会退化成 O(n²) 直接超时，而单调队列把「每个窗口重新求最值」压缩成「每个元素只进出队列一次」，因此选它作为最优解。

CodeTop 变体

#76 最小覆盖子串

题意

给定字符串 s 和 t，返回 s 中涵盖 t 所有字符的最短子串；若不存在，返回空串 ""。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

「涵盖所有字符」要求的是数量：t 中某字符出现 m 次，s 的子串中该字符至少出现 m 次才算覆盖，且 t 里的字符可能在 s 中夹杂其他无关字符。

难点与易错点

  1. 「覆盖」是计数问题，不是集合问题：t = "AABC" 时子串里必须有两个 A。只用 Set 去重判断会漏掉「重复字符」的情况，必须用频次 map 精确比较数量。
  2. Integer 比较的缓存陷阱：window.get(c) 返回的是 Integer 对象，用 == 比较时，只有值在 -128 ~ 127 之间才会命中缓存（字符频次很容易超过 127，或作为对象比较时出问题）。必须用 .equals() 比较，否则 valid 计数错误，窗口永远判不合法。
  3. valid 只在「刚好等于」时变化：只有 window.get(c).equals(need.get(c))（从「不足」到「刚好满足」的瞬间）才 valid++；同理收缩时从「刚好满足」到「不足」才 valid--。若写成 >= 会导致同一字符被重复计数。
  4. 收缩的时机与顺序：每次 right 右移后都要尝试「只要窗口还合法就不断收缩 left」，收缩前先记录当前是否为最小窗口，先更新再收缩，否则会漏掉最小答案。

解法一：暴力 / 直观

枚举 s 的所有子串 [i, j]，对每个子串判断是否覆盖 t，更新最小长度：

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length();
        int minLen = Integer.MAX_VALUE;
        int start = 0;
        // 枚举所有子串 [i, j)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                String sub = s.substring(i, j);
                if (covers(sub, t) && j - i < minLen) {
                    minLen = j - i;
                    start = i;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    // 判断 sub 是否覆盖 t 的所有字符
    private boolean covers(String sub, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        int[] have = new int[128];
        for (char c : sub.toCharArray()) have[c]++;
        for (int i = 0; i < 128; i++) {
            if (have[i] < need[i]) return false;
        }
        return true;
    }
}

复杂度：子串共有 n(n+1)/2 个，即 O(n²)；每个子串要做一次 covers 判定，扫描子串 O(n) + 固定 128 次比较，故整体 O(n³)；空间 O(1)（固定 128 数组）。

瓶颈在哪：一是子串数量 O(n²) 太多；二是相邻子串之间大量重叠，covers 每次都从头统计频次，重复劳动；三是 substring 本身还会产生 O(n) 的字符串复制开销。三重叠加，n 稍大就不可用。

解法二：优化 / 最优（可变长滑动窗口）

题目本质：一个可变长滑动窗口 + 字符覆盖计数问题。right 指针向右扩张，直到窗口覆盖 t 的所有字符；然后收缩 left 使窗口尽可能小，期间记录最小窗口。

现实类比：找最小背包。需要凑齐 t 中的所有食材（可能包含重复），在货架 s 上向右扫描，凑齐后尝试从左侧「退货」缩小清单，最终找到最小的、能满足需求的清单范围。

容器选择：两个 HashMap<Character, Integer>——need 记录 t 中每个字符的需求量，window 记录当前窗口中每个字符的实际数量；valid 记录已满足需求的字符种类数，当 valid == need.size() 时窗口合法。比较频次必须用 .equals() 而非 ==（Integer 缓存陷阱）。

三步主线：

  1. 构建 need map，right 右移把字符加入 window；若 window.get(c).equals(need.get(c))，则 valid++；
  2. 当 valid == need.size() 时窗口合法：更新最小窗口，然后收缩 left 直到不再合法；
  3. 重复直到 right 到达末尾。
class Solution {
    public String minWindow(String s, String t) {
        // need: t 中每个字符的需求频次
        Map<Character, Integer> need = new HashMap<>();
        // window: 当前滑动窗口内每个字符的实际频次
        Map<Character, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.merge(c, 1, Integer::sum);
        }

        int left = 0, right = 0;
        int valid = 0;      // 已满足需求的字符种类数
        int start = 0;      // 最小窗口的起始位置
        int minLen = Integer.MAX_VALUE; // 最小窗口长度

        while (right < s.length()) {
            char entering = s.charAt(right++);

            // 只关心 need 中的字符，无关字符直接忽略
            if (need.containsKey(entering)) {
                window.merge(entering, 1, Integer::sum);
                // 使用 equals 比较 Integer，避免 == 在值 > 127 时的缓存陷阱
                if (window.get(entering).equals(need.get(entering))) {
                    valid++;
                }
            }

            // 窗口覆盖了 t 的所有字符：尝试收缩左边界
            while (valid == need.size()) {
                // 更新最小覆盖子串
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                char leaving = s.charAt(left++);

                if (need.containsKey(leaving)) {
                    // 离开前若该字符频次正好满足需求，收缩后 valid 减少
                    if (window.get(leaving).equals(need.get(leaving))) {
                        valid--;
                    }
                    window.merge(leaving, -1, Integer::sum);
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

> **💭 思考**：为什么这题用「可变长滑动窗口 + need/window/valid」这套状态，而不是暴力枚举每个子串？一步步想——暴力的瓶颈有三重：子串数量 O(n²)、每个子串的 `covers` 都从头重新统计频次、`substring` 还产生字符串复制。看到「在 s 里找覆盖 t 的最短连续子串」，「连续 + 最短」就是滑动窗口的强信号。但「覆盖」是计数问题而非集合问题，所以要精确记录频次，于是有了 `need`（需求）和 `window`（当前拥有）两张表；而每次重新比对 O(字符集) 太慢，就想出一个 `valid` 计数器，只在「某字符从不足到刚好满足」的瞬间 +1，把「是否覆盖」的判断压到 O(1)——这就是 `valid == need.size()` 的由来。

复杂度逐步推导：

多解法对比

解法时间复杂度空间复杂度适用场景
暴力枚举O(n³)O(1)仅用于理解题意
滑动窗口O(n)O(字符集)本题最优，双指针均摊线性

本题约束下（s、t 长度可达 10⁵），暴力法 O(n³) 完全不可行；滑动窗口利用「窗口合法则收缩、不合法则扩张」的单调性，让两个指针各走一遍，得到线性时间。空间上用 HashMap 还是 128 长度 int 数组取决于面试官的字符集范围要求，本质一致。

CodeTop 变体

章末提问

  1. #560 为什么不能用滑动窗口，只能前缀和 + 哈希？——结论：因为数组含负数，前缀和不再单调，窗口「该不该收缩」无法判断——收缩丢掉一个负数后和反而变大。前缀和把「区间和」转成「两个前缀和之差」，绕开了对单调性的依赖。
  2. #239 单调队列里 while 嵌套 while，为什么是 O(n)？——结论：因为每个元素入队、出队各一次，n 个元素总共 2n 次操作。内层 while 弹掉的元素不会再第二次入队，均摊到每个元素是常数。
  3. #76 里 valid 为什么只在「刚好等于 need」时增减，用 >= 会怎样？——结论：用 >= 会让同一个字符反复触发 valid++，导致 valid 虚高、窗口被错误判定为已覆盖。只有「从不足到刚好满足」这一瞬间才计数，才能精确反映「已满足的字符种类数」。
Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
前缀和+哈希表——子数组问题的万能钥匙
Next Post
原地哈希——把数组本身当成哈希表