跳到主要内容

子串问题

子串类题目通常涉及对连续片段的处理，可能结合前缀和、滑动窗口、或单调队列等技巧。这类问题的核心特点是需要在字符串或数组的连续区间上操作，而非离散的元素选择。

子串问题与子序列问题的区别在于：子串要求元素在原串中连续，而子序列不要求。这一区别导致了解题方法的显著差异——子串问题通常可以用滑动窗口或前缀和技术高效解决。

560. 和为 K 的子数组 (Subarray Sum Equals K)​

题目描述​

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

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

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
解释：[1,1] 与 [1,1] 为两种不同的情况。

示例 2：

输入：nums = [1,2,3], k = 3
输出：2
解释：子数组 [1,2] 和 [3] 的和都为 3。

示例 3：

输入：nums = [1,-1,0], k = 0
输出：3
解释：子数组 [1,-1]、[-1,0]、[0] 的和都为 0。

约束条件：

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

解题思路​

这道题要求统计和为 k 的子数组个数。关键在于如何高效地计算子数组的和。

方法一：暴力枚举（不推荐）​

使用两层循环枚举所有子数组，计算每个子数组的和。时间复杂度 O(n²)，当数组长度达到 10^4 时会超时。

方法二：前缀和 + 哈希表（推荐）​

前缀和是一个经典的预处理技巧。定义 prefix[i] 表示从数组开头到第 i 个元素的和。那么子数组 nums[i..j] 的和可以表示为 prefix[j] - prefix[i-1]。

如果我们想找和为 k 的子数组，就是要找到 i 和 j，使得 prefix[j] - prefix[i-1] = k，即 prefix[i-1] = prefix[j] - k。

这意味着：当我们遍历到位置 j 时，只需要统计之前有多少个前缀和等于 prefix[j] - k。这正是哈希表擅长的事情——用 O(1) 时间统计某个值出现的次数。

图解示例​

以 nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7 为例：

前缀和数组：
prefix[-1] = 0（虚拟前缀和，表示空前缀）
prefix[0] = 3
prefix[1] = 3 + 4 = 7
prefix[2] = 7 + 7 = 14
prefix[3] = 14 + 2 = 16
prefix[4] = 16 + (-3) = 13
prefix[5] = 13 + 1 = 14
prefix[6] = 14 + 4 = 18
prefix[7] = 18 + 2 = 20

遍历过程：
哈希表记录前缀和出现的次数，初始 {0: 1}

i=0: prefix = 3
  需要找 prefix - k = 3 - 7 = -4
  -4 不在哈希表中
  更新哈希表：{0:1, 3:1}

i=1: prefix = 7
  需要找 prefix - k = 7 - 7 = 0
  0 在哈希表中，次数为 1
  找到 1 个符合条件的子数组！
  更新哈希表：{0:1, 3:1, 7:1}

i=2: prefix = 14
  需要找 prefix - k = 14 - 7 = 7
  7 在哈希表中，次数为 1
  找到 1 个符合条件的子数组！
  更新哈希表：{0:1, 3:1, 7:1, 14:1}

i=3: prefix = 16
  需要找 prefix - k = 16 - 7 = 9
  9 不在哈希表中
  更新哈希表：{..., 16:1}

i=4: prefix = 13
  需要找 prefix - k = 13 - 7 = 6
  6 不在哈希表中
  更新哈希表：{..., 13:1}

i=5: prefix = 14
  需要找 prefix - k = 14 - 7 = 7
  7 在哈希表中，次数为 1
  找到 1 个符合条件的子数组！
  更新哈希表：{..., 14:2}

i=6: prefix = 18
  需要找 prefix - k = 18 - 7 = 11
  11 不在哈希表中
  更新哈希表：{..., 18:1}

i=7: prefix = 20
  需要找 prefix - k = 20 - 7 = 13
  13 在哈希表中，次数为 1
  找到 1 个符合条件的子数组！
  更新哈希表：{..., 20:1}

总计：4 个子数组的和为 7
分别是：[3,4]、[7]、[7,2,-3,1]、[1,4,2]

Java 代码实现​

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 结果计数器
        int result = 0;
        // 当前前缀和
        int prefixSum = 0;
        // 哈希表：键为前缀和，值为该前缀和出现的次数
        Map<Integer, Integer> prefixCount = new HashMap<>();
        
        // 初始化：空前缀的和为 0，出现 1 次
        // 这一步很关键，用于处理从数组开头开始的子数组
        prefixCount.put(0, 1);
        
        for (int num : nums) {
            // 更新前缀和
            prefixSum += num;
            
            // 查找有多少个前缀和等于 (prefixSum - k)
            // 如果存在，说明从那些位置到当前位置的子数组和为 k
            if (prefixCount.containsKey(prefixSum - k)) {
                result += prefixCount.get(prefixSum - k);
            }
            
            // 将当前前缀和加入哈希表
            prefixCount.put(prefixSum, prefixCount.getOrDefault(prefixSum, 0) + 1);
        }
        
        return result;
    }
}

复杂度分析​

时间复杂度：O(n)，只需要遍历数组一次，每次哈希表操作都是 O(1)。

空间复杂度：O(n)，最坏情况下哈希表需要存储 n 个不同的前缀和。

易错点​

  1. 忘记初始化哈希表：必须初始化 {0: 1}，表示空前缀和为 0，用于处理从数组开头开始的子数组。

  2. 操作顺序错误：必须先查找再更新哈希表。如果先更新再查找，可能会把当前位置的前缀和也算进去，导致错误。

  3. 不能用滑动窗口：这道题的数组包含负数，前缀和不单调，无法使用滑动窗口。滑动窗口适用于前缀和单调的情况。

为什么不能用滑动窗口？​

滑动窗口的核心思想是利用单调性：当窗口扩大时，某个指标单调变化。但在这道题中：

  • 数组可能包含负数
  • 扩大窗口可能增加和，也可能减少和
  • 无法通过简单的窗口调整来判断是否满足条件

因此前缀和 + 哈希表是这道题的最优解。

239. 滑动窗口最大值 (Sliding Window Maximum)​

题目描述​

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

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
窗口位置                最大值
---------------        -----
[1  3  -1] -3  5  3  6  7      3
 1 [3  -1  -3] 5  3  6  7      3
 1  3 [-1  -3  5] 3  6  7      5
 1  3  -1 [-3  5  3] 6  7      5
 1  3  -1  -3 [5  3  6] 7      6
 1  3  -1  -3  5 [3  6  7]     7

示例 2：

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

约束条件：

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

解题思路​

这道题要求在滑动窗口中快速获取最大值。暴力方法需要对每个窗口遍历 k 个元素，时间复杂度 O(n×k)。

方法一：最大堆（优先队列）​

使用最大堆维护窗口内的元素。每次窗口滑动时，将新元素加入堆，并移除堆顶超出窗口范围的元素。

时间复杂度 O(n log n)，因为堆的大小可能达到 n。

方法二：单调双端队列（推荐）​

使用一个双端队列维护一个单调递减的序列。队列中存储数组下标，保证队列前端始终是当前窗口的最大值。

核心思想：

  • 新元素进入窗口时，从队尾移除所有比它小的元素（它们不可能成为最大值）
  • 队首元素如果超出窗口范围，从队首移除
  • 队列保持单调递减，队首就是最大值

图解示例​

以 nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 为例：

初始状态：deque = []

i=0, nums[0]=1:
  deque 为空，直接加入
  deque = [0]（存储下标，对应值 [1]）

i=1, nums[1]=3:
  3 > nums[deque.back] = 1，弹出队尾
  deque = []，然后加入 1
  deque = [1]（对应值 [3]）

i=2, nums[2]=-1:
  -1 < nums[deque.back] = 3，直接加入
  deque = [1, 2]（对应值 [3, -1]）
  窗口形成！最大值为 nums[deque[0]] = 3

i=3, nums[3]=-3:
  -3 < nums[deque.back] = -1，直接加入
  deque = [1, 2, 3]（对应值 [3, -1, -3]）
  检查队首：deque[0] = 1，窗口范围 [1,3]，在窗口内
  最大值为 nums[deque[0]] = 3

i=4, nums[4]=5:
  5 > nums[deque.back] = -3，弹出队尾
  deque = [1, 2]
  5 > nums[deque.back] = -1，弹出队尾
  deque = [1]
  5 > nums[deque.back] = 3，弹出队尾
  deque = []，然后加入 4
  deque = [4]（对应值 [5]）
  检查队首：deque[0] = 4，窗口范围 [2,4]，在窗口内
  最大值为 nums[deque[0]] = 5

i=5, nums[5]=3:
  3 < nums[deque.back] = 5，直接加入
  deque = [4, 5]（对应值 [5, 3]）
  检查队首：deque[0] = 4，窗口范围 [3,5]，在窗口内
  最大值为 nums[deque[0]] = 5

i=6, nums[6]=6:
  6 > nums[deque.back] = 3，弹出队尾
  deque = [4]
  6 > nums[deque.back] = 5，弹出队尾
  deque = []，然后加入 6
  deque = [6]（对应值 [6]）
  检查队首：deque[0] = 6，窗口范围 [4,6]，在窗口内
  最大值为 nums[deque[0]] = 6

i=7, nums[7]=7:
  7 > nums[deque.back] = 6，弹出队尾
  deque = []，然后加入 7
  deque = [7]（对应值 [7]）
  检查队首：deque[0] = 7，窗口范围 [5,7]，在窗口内
  最大值为 nums[deque[0]] = 7

最终结果：[3, 3, 5, 5, 6, 7]

Java 代码实现​

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 结果数组，长度为 n - k + 1
        int[] result = new int[n - k + 1];
        // 双端队列存储下标，保持单调递减
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 移除超出窗口范围的元素
            // 如果队首元素的下标 <= i - k，说明已经不在窗口内
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            
            // 维护单调递减：移除所有比当前元素小的队尾元素
            // 因为这些元素不可能成为后续窗口的最大值
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            // 将当前元素下标加入队尾
            deque.offerLast(i);
            
            // 当 i >= k - 1 时，窗口形成，记录最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

复杂度分析​

时间复杂度：O(n)，每个元素最多入队一次、出队一次。

空间复杂度：O(k)，双端队列最多存储 k 个元素。

为什么存下标而不是值？​

这是一个关键问题。存储下标有两个优势：

  1. 判断是否在窗口内：通过下标可以判断元素是否超出窗口范围。如果只存值，无法判断。

  2. 处理重复值：当数组中有重复元素时，存储下标可以区分它们。

易错点​

  1. 使用 while 而非 if：移除队尾元素和移除超出窗口的元素都需要用 while 循环，因为可能需要移除多个元素。

  2. 边界条件：当 i < k - 1 时窗口还未形成，不应记录结果。

  3. 比较时用下标取值：注意 nums[deque.peekLast()] < nums[i]，是比较值而不是下标。

76. 最小覆盖子串 (Minimum Window Substring)​

题目描述​

给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符（包括重复字符）的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3：

输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 应包含在 s 的子串中，但 s 中只有一个 'a'。

约束条件：

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10^5
  • s 和 t 由英文字母组成

解题思路​

这道题要求找到包含目标字符串所有字符的最短子串，是一个典型的变长滑动窗口问题。

方法：滑动窗口 + 字符计数​

核心思想是维护一个可变大小的窗口，动态调整窗口的左右边界：

  1. 扩展窗口：右指针向右移动，将新字符加入窗口
  2. 检查条件：判断窗口是否包含 t 的所有字符
  3. 收缩窗口：如果满足条件，尝试移动左指针缩小窗口

关键在于如何高效判断窗口是否满足条件。我们可以用两个计数器：

  • need[c]：字符 c 在 t 中需要的数量
  • have[c]：字符 c 在当前窗口中的数量

图解示例​

以 s = "ADOBECODEBANC", t = "ABC" 为例：

need = {A:1, B:1, C:1}
窗口初始为空

第1步：right=0, s[0]='A'
  have = {A:1}
  有效字符数 = 1（A 满足需求）
  
第2步：right=1, s[1]='D'
  have = {A:1, D:1}
  有效字符数 = 1（D 不需要）
  
第3步：right=2, s[2]='O'
  have = {A:1, D:1, O:1}
  有效字符数 = 1
  
第4步：right=3, s[3]='B'
  have = {A:1, D:1, O:1, B:1}
  有效字符数 = 2（A, B 满足）
  
第5步：right=4, s[4]='E'
  have = {A:1, D:1, O:1, B:1, E:1}
  有效字符数 = 2
  
第6步：right=5, s[5]='C'
  have = {A:1, D:1, O:1, B:1, E:1, C:1}
  有效字符数 = 3（A, B, C 都满足！）
  
  窗口满足条件！尝试收缩：
  left=0, s[0]='A'，是必要字符，不能移除
  记录当前最小窗口：长度 6，起始位置 0
  
第7步：继续收缩
  left=0, s[0]='A'，移除后不满足条件
  有效字符数 = 2
  窗口变为 "DOBECO..."，不满足条件
  
第8步：right=6, s[6]='O'
  继续扩展...
  
... 省略中间步骤 ...

最终在第 9 步找到更小的窗口：
  窗口 "BANC"，长度 4，起始位置 9
  
最终结果："BANC"

Java 代码实现​

class Solution {
    public String minWindow(String s, String t) {
        // 边界条件
        if (s == null || s.length() == 0 || t == null || t.length() == 0) {
            return "";
        }
        
        // 记录 t 中每个字符需要的数量
        int[] need = new int[128];
        // 记录当前窗口中每个字符的数量
        int[] have = new int[128];
        
        // 统计 t 中字符
        for (char c : t.toCharArray()) {
            need[c]++;
        }
        
        // 需要满足的字符种类数
        int needCount = 0;
        for (int count : need) {
            if (count > 0) needCount++;
        }
        
        // 当前已满足的字符种类数
        int haveCount = 0;
        // 最小窗口的起始位置和长度
        int minStart = -1, minLen = Integer.MAX_VALUE;
        // 左右指针
        int left = 0, right = 0;
        
        while (right < s.length()) {
            char c = s.charAt(right);
            
            // 如果当前字符是需要的字符
            if (need[c] > 0) {
                have[c]++;
                // 如果该字符数量刚好满足要求
                if (have[c] == need[c]) {
                    haveCount++;
                }
            }
            
            // 当窗口满足所有字符要求时，尝试收缩
            while (haveCount == needCount) {
                // 更新最小窗口
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                
                // 移除左边界字符
                char leftChar = s.charAt(left);
                if (need[leftChar] > 0) {
                    // 如果移除后不再满足该字符的数量要求
                    if (have[leftChar] == need[leftChar]) {
                        haveCount--;
                    }
                    have[leftChar]--;
                }
                left++;
            }
            
            right++;
        }
        
        return minStart == -1 ? "" : s.substring(minStart, minStart + minLen);
    }
}

复杂度分析​

时间复杂度：O(m + n)，其中 m 是 s 的长度，n 是 t 的长度。每个字符最多被访问两次（右指针一次，左指针一次）。

空间复杂度：O(1)，使用固定大小的数组（128 个字符），不随输入规模变化。

易错点​

  1. 判断满足条件的逻辑：不是简单比较字符数量，而是要判断每个需要的字符是否都达到了要求数量。

  2. 收缩窗口的时机：只有当窗口满足所有条件时才收缩，不满足时应该继续扩展。

  3. 重复字符的处理：t 中可能有重复字符，需要统计每个字符的出现次数，而不是只记录是否出现过。

优化技巧​

使用数组代替哈希表可以提升性能，因为字符集是有限的（ASCII 字符）。如果字符集更大或不确定，可以使用哈希表。

相关题目​