Dorian's Blog

字串

1 和为 K 的子数组

【原始题目】

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

子数组是数组中元素的连续非空序列。

示例 1：输入：nums = [1,1,1], k = 2 输出：2

示例 2：输入：nums = [1,2,3], k = 3 输出：2

提示： 1 <= nums.length <= 2 * 10^4 -1000 <= nums[i] <= 1000 -10^7 <= k <= 10^7

【题目速记】

整数数组，元素有正有负。求连续子数组的和等于 k 的个数，返回个数。数组长度最大 2 万。

【题解】

一句话速通：先构建前缀和数组，然后双重循环枚举所有子数组，用前缀和之差判断和是否为 k 并计数。

【算法思想】

前缀和：预处理数组，使任意子数组和可以在 $O(1)$ 时间内得到，避免重复累加。

【核心思路】

创建长度 n+1 的前缀和数组 preSum，preSum[i] 表示 nums[0..i-1] 的和。
双重循环：外层 i 从 0 到 n-1 表示子数组起点，内层 j 从 i 到 n-1 表示终点。
子数组 nums[i..j] 的和为 preSum[j+1] - preSum[i]，若等于 k 则计数器加一。
返回计数结果。

【复杂度】

时间复杂度 $O(n^2)$ ：两层循环遍历所有子数组，每次判断为 $O(1)$ 。
空间复杂度 $O(n)$ ：前缀和数组占用线性空间。

【伪代码】

text

preSum[0] = 0
for i from 1 to n:
    preSum[i] = preSum[i-1] + nums[i-1]

count = 0
for left from 0 to n-1:
    for right from left to n-1:
        if preSum[right+1] - preSum[left] == k:
            count++
return count

【易错点】

前缀和索引容易搞混：子数组 nums[i..j] 的和是 preSum[j+1] - preSum[i]。
内层循环的右边界需要从 i 开始，保证子数组非空。

【完整代码】

java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] preSum = new int[n + 1];
        for (int i = 0; i &lt; n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int count = 0;
        for (int left = 0; left &lt; n; left++) {
            for (int right = left; right &lt; n; right++) {
                if (preSum[right + 1] - preSum[left] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

【题解】

一句话速通：一边遍历一边维护当前前缀和，用哈希表记录历史前缀和的出现次数，通过查找当前前缀和减去 k 的出现次数来统计子数组个数。

【算法思想】

前缀和：将子数组和转化为两个前缀和之差。
哈希表：快速查询前缀和出现次数，实现 $O(n)$ 统计。

【核心思路】

初始化哈希表，放入 (0, 1)，表示前缀和为 0 出现了一次，用于处理从数组开头开始的子数组。
遍历数组，累加当前前缀和 sum。
在将 sum 加入哈希表之前，先查哈希表中 sum - k 出现的次数，累加到结果 count。
然后将当前 sum 出现次数加一，更新哈希表。
遍历结束返回 count。

【复杂度】

时间复杂度 $O(n)$ ：只需一次遍历，哈希表插入和查询均为 $O(1)$ 。
空间复杂度 $O(n)$ ：最坏情况下哈希表存储所有不同前缀和。

【伪代码】

text

map.put(0, 1)
sum = 0, count = 0
for num in nums:
    sum += num
    if map contains (sum - k):
        count += map.get(sum - k)
    map.put(sum, map.getOrDefault(sum, 0) + 1)
return count

【易错点】

查询与更新的顺序：必须先查询 sum - k 再更新 sum，否则 k 为 0 时会错误地把当前前缀和自己算进去。
务必初始化 map.put(0, 1)，否则会漏掉从索引 0 开始的满足条件的子数组。

【完整代码】

java

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map&lt;Integer, Integer> map = new HashMap&lt;>();
        map.put(0, 1);

        int sum = 0;
        int count = 0;
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

2 滑动窗口最大值

【原始题目】

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值构成的数组。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

示例 2：

输入：nums = [1], k = 1 输出：[1]

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

【题目速记】

给定数组和固定窗口大小 k，窗口从左向右每次滑动一格，每次输出窗口内的最大值。结果是一个数组，长度是 n - k + 1。元素有正有负，数据规模到 $10^5$，需要高效解法。

【题解】

一句话速通：用大顶堆实时维护窗口内元素，存数值和下标，每次取堆顶前剔除已滑出窗口的元素，堆顶就是当前窗口最大值。

【算法思想】

优先队列（大顶堆）：快速获取窗口内最大值，每次取堆顶即可。
延迟删除：当堆顶元素的下标已经滑出窗口左边界时，再弹出它，避免实时删除带来的复杂度。

【核心思路】

创建一个最大堆（Java 中用 PriorityQueue 并自定义比较器按数值降序），堆中存 [值, 下标] 对。
遍历数组，下标 i 从 0 到 n-1，把当前元素加入堆。
当窗口形成时（即 i >= k-1），窗口左边界是 i - k + 1。
反复检查堆顶元素的下标是否小于左边界，如果是就弹出堆顶（它已经无效了）。
经过清理后，堆顶元素的值就是当前窗口最大值，加入结果数组。
继续向右滑动，直到遍历结束。

【复杂度】

时间复杂度 $O(n \log n)$ ：每个元素入堆一次、最多出堆一次，堆操作是 $O(\log n)$，总体最坏 $O(n \log n)$。
空间复杂度 $O(n)$ ：堆最多存储所有元素。

【伪代码】

text

初始化 大顶堆 pq，存放 (num, index)，按 num 降序排列
结果数组 res，长度 n - k + 1

遍历 i 从 0 到 n-1：
    pq.offer((nums[i], i))

    如果 i >= k-1：
        窗口左边界 left = i - k + 1
        
        当 pq 堆顶的下标 &lt; left 时：
            pq.poll()
        
        res[left] = pq.peek().num

返回 res

【易错点】

堆中必须同时存值和下标，只存值无法判断元素是否已经滑出窗口。
仅在窗口形成后（i >= k-1）才记录结果，不要提前记录。
清理堆顶要用 while 循环，可能连续多个元素都失效了。

【完整代码】

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        
        // 大顶堆：int[0]是值，int[1]是下标，按值降序
        PriorityQueue&lt;int[]> pq = new PriorityQueue&lt;>((a, b) -> b[0] - a[0]);
        
        for (int i = 0; i &lt; n; i++) {
            pq.offer(new int[]{nums[i], i});
            
            // 窗口形成
            if (i >= k - 1) {
                int left = i - k + 1;
                // 移除不在当前窗口内的元素
                while (pq.peek()[1] &lt; left) {
                    pq.poll();
                }
                res[left] = pq.peek()[0];
            }
        }
        return res;
    }
}

【题解】

一句话速通：用一个单调递减的双端队列存下标，保证队首始终是窗口最大值，每次移动时维护队列单调性并移除过期元素，直接取队首即可。

【算法思想】

单调队列（单调递减）：队列中的元素值从队首到队尾严格递减，队首就是当前窗口最大值。
双端队列：允许在两端高效增删，用来维护这个单调性并剔除过期下标。

【核心思路】

使用 Deque 存储下标，保证队列中下标对应的 nums 值严格递减。
遍历数组，下标 i 从 0 到 n-1：
- 如果队首下标已经滑出左边界（< i - k + 1），移除队首。
- 从队尾开始，把小于等于当前值的元素下标全部移除（维持单调递减）。
- 将当前下标 i 加入队尾。
当窗口形成（i >= k-1）时，队首下标对应的值就是当前窗口最大值，记录到结果中。
继续向右滑动直到结束。

【复杂度】

时间复杂度 $O(n)$ ：每个元素最多入队一次、出队一次，所有操作均摊 $O(1)$。
空间复杂度 $O(k)$ ：队列中最多同时存 $k$ 个元素。

【伪代码】

text

初始化 Deque&lt;Integer> deque 存下标
结果数组 res，长度 n - k + 1

遍历 i 从 0 到 n-1：
    // 1. 移除窗口左侧的过期元素
    如果 deque 非空 且 deque队首 &lt; i - k + 1：
        deque.removeFirst()
    
    // 2. 维持单调递减
    当 deque 非空 且 nums[deque队尾] &lt;= nums[i]：
        deque.removeLast()
    
    // 3. 当前元素入队
    deque.addLast(i)
    
    // 4. 记录结果
    如果 i >= k - 1：
        res[i - k + 1] = nums[deque队首]

返回 res

【易错点】

队列里存的是下标，不是值，这样才能判断元素是否滑出窗口。
维持单调递减时，条件是 nums[deque.peekLast()] <= nums[i]，等号不要漏，因为新的元素更靠右，旧的相等值已经不可能成为最大值，应当被移除。
判断过期条件：队首下标 < i - k + 1，不是 <=。

【完整代码】

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque&lt;Integer> deque = new ArrayDeque&lt;>();
        
        for (int i = 0; i &lt; n; i++) {
            // 移除滑出窗口的下标
            if (!deque.isEmpty() && deque.peekFirst() &lt; i - k + 1) {
                deque.pollFirst();
            }
            
            // 保持单调递减
            while (!deque.isEmpty() && nums[deque.peekLast()] &lt;= nums[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            
            // 窗口形成后记录结果
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}

3 最小覆盖子串

【原始题目】

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

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

示例 2：输入：s = "a", t = "a" 输出："a"

示例 3：输入：s = "a", t = "aa" 输出：""

提示： m == s.length n == t.length 1 <= m, n <= 105 s 和 t 由英文字母组成

进阶：你能设计一个在 $O(m + n)$ 时间内解决此问题的算法吗？

【题目速记】

在 s 中找一个最短的子串，必须覆盖 t 中所有字符（包括重复次数）。找不到返回 ""。字符串仅含英文字母，长度可达 $10^5$，要求 $O(m + n)$ 解法。

【题解】

一句话速通：滑动窗口 + 需求计数表，用 needCount 记录仍缺字符总数，右扩左缩的经典模板一遍扫描。

【算法思想】

滑动窗口：双指针维护一个动态窗口，在 s 上滑动寻找满足条件的最短区间。
计数数组（或哈希表）：用长度为 128 的数组统计 t 中每个字符的需求次数，O(1) 判断是否覆盖。

【核心思路】

用数组 need[128] 记录 t 中每个字符还需多少个，needCount = t.length() 表示总共还需要匹配的字符数。
右指针 r 遍历 s，将 s[r] 加入窗口。如果 need[s[r]] > 0，说明该字符是当前需要的，needCount--；然后 need[s[r]]--（无论如何都减）。
当 needCount == 0 时，窗口已经覆盖 t。此时不断尝试右移左指针 l 收缩窗口：
- 如果 need[s[l]] == 0，说明左指针字符刚好满足需求，再移走就会导致缺字符，此时更新最小窗口并跳出收缩。
- 如果 need[s[l]] < 0，说明该字符在窗口中有多余，可以安全移走，执行 need[s[l]]++，l++。
收缩结束后，用 r - l + 1 更新最短窗口的起止索引。右指针继续前进。
最后根据记录的起止点截取子串，未找到则返回 ""。

【复杂度】

时间复杂度 $O(m + n)$ ：每个字符被左右指针各访问一次。
空间复杂度 $O(1)$ ：数组大小固定 128，与输入规模无关。

【伪代码】

text

need[128] = 0, needCount = t.length()
for c in t: need[c]++

l = 0, minLen = MAX, start = 0
for r from 0 to s.length()-1:
    c = s[r]
    if need[c] > 0: needCount--
    need[c]--

    while needCount == 0:
        if r - l + 1 &lt; minLen:
            minLen = r - l + 1
            start = l
        leftChar = s[l]
        if need[leftChar] == 0:
            needCount++
        need[leftChar]++
        l++

return minLen == MAX ? "" : s.substring(start, start + minLen)

【易错点】

needCount 的更新条件：只有 need[c] > 0 才减，因为需求 ≤0 时说明该字符已经多余或不在 t 中。
收缩时，左指针字符 need[leftChar] == 0 表示刚好满足需求，移走它会导致 needCount 增加；< 0 则只是去除多余字符，不改变 needCount。
更新 minLen 必须在收缩循环内部，因为此时窗口有效且可能更小。
数组开 128 足以覆盖所有大小写字母的 ASCII 码。

【完整代码】

Java

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        int needCount = t.length();
        for (char c : t.toCharArray()) {
            need[c]++;
        }

        int l = 0;
        int minLen = Integer.MAX_VALUE;
        int start = 0;

        for (int r = 0; r &lt; s.length(); r++) {
            char c = s.charAt(r);
            if (need[c] > 0) {
                needCount--;
            }
            need[c]--;

            while (needCount == 0) {
                if (r - l + 1 &lt; minLen) {
                    minLen = r - l + 1;
                    start = l;
                }
                char leftChar = s.charAt(l);
                if (need[leftChar] == 0) {
                    needCount++;
                }
                need[leftChar]++;
                l++;
            }
        }

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

【题解】

一句话速通：同样滑动窗口，但改用“已满足字符种类数” matched 来判断覆盖，避免频繁检查 needCount，逻辑更清晰、扩展性更强。

【算法思想】

滑动窗口：同模板。
计数 + 状态变量：用 matched 记录“当前已满足需求的字符种类数”，与需求表 need 和窗口表 window 配合。

【核心思路】

统计 t 中字符频率 need[128]，并记录不同字符的种类数 required。
维护窗口频率 window[128]，右指针 r 扩展：每次将 window[s[r]]++，若该字符在 need 中的次数 > 0 且 window 中次数刚好等于 need 中的次数，则 matched++。
当 matched == required 时，窗口已覆盖，尝试收缩左指针 l：
- 先记录当前更小的窗口。
- 移出左指针字符前，若该字符在 need 中且 window 中的次数等于 need 中的次数，则 matched--。
- 然后 window[leftChar]--，l++，直到窗口不再满足覆盖。
重复上述过程直至遍历结束。

【复杂度】

时间复杂度 $O(m + n)$ ：每个字符最多被访问两次。
空间复杂度 $O(1)$ ：固定 128 大小的辅助数组。

【伪代码】

text

need[128] = 0, required = 0
for c in t:
    if need[c] == 0: required++
    need[c]++

window[128] = 0
l = 0, matched = 0, minLen = MAX, start = 0

for r from 0 to s.length()-1:
    c = s[r]
    window[c]++
    if need[c] > 0 and window[c] == need[c]:
        matched++

    while matched == required:
        if r - l + 1 &lt; minLen:
            minLen = r - l + 1
            start = l
        leftChar = s[l]
        if need[leftChar] > 0 and window[leftChar] == need[leftChar]:
            matched--
        window[leftChar]--
        l++

return minLen == MAX ? "" : s.substring(start, start + minLen)

【易错点】

required 只统计 t 中出现过的不同字符种类，不要把重复字符算入。
matched 增加的条件是 window[c] == need[c] 且 need[c] > 0，注意是“刚好达到需求”这一刻增加，之后再增加不会改变 matched。
收缩时，matched 减少的条件是移出字符后不再满足需求，即 window[leftChar] == need[leftChar] 且 need[leftChar] > 0，然后在 window[leftChar]-- 之前判断。
数组长度仍用 128，覆盖所有大小写字母。

【完整代码】

Java

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        int required = 0;
        for (char c : t.toCharArray()) {
            if (need[c] == 0) required++;
            need[c]++;
        }

        int[] window = new int[128];
        int l = 0;
        int matched = 0;
        int minLen = Integer.MAX_VALUE;
        int start = 0;

        for (int r = 0; r &lt; s.length(); r++) {
            char c = s.charAt(r);
            window[c]++;
            if (need[c] > 0 && window[c] == need[c]) {
                matched++;
            }

            while (matched == required) {
                if (r - l + 1 &lt; minLen) {
                    minLen = r - l + 1;
                    start = l;
                }
                char leftChar = s.charAt(l);
                if (need[leftChar] > 0 && window[leftChar] == need[leftChar]) {
                    matched--;
                }
                window[leftChar]--;
                l++;
            }
        }

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

字串 ​

1 和为 K 的子数组 ​

【原始题目】 ​

【题目速记】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

2 滑动窗口最大值 ​

【原始题目】 ​

【题目速记】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

3 最小覆盖子串 ​

【原始题目】 ​

【题目速记】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

字串

1 和为 K 的子数组

【原始题目】

【题目速记】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

2 滑动窗口最大值

【原始题目】

【题目速记】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

3 最小覆盖子串

【原始题目】

【题目速记】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】