迎风起降的小站
子串
蜂窝煤 Lv3
  2026-09-19 10:00:00   2026-09-22 14:53:05    

子串是字符串中连续的一段字符，子数组则是数组中连续的一段元素。两者都强调连续性，这也是这类问题最重要的特征：通常可以把答案表示为一个区间 [left, right]，再围绕区间的左右边界设计高效算法。

需要注意，子串或子数组和子序列不同。子序列可以删除中间元素，只要求保留元素的相对顺序；子串和子数组则不能跳过任何元素。

基本思路

解决子串问题时，通常先明确以下三个问题：

  1. 当前区间如何表示：使用 [left, right] 或 [left, right) 表示一个连续区间。
  2. 区间状态如何维护：根据题目要求维护区间和、字符频次、不同字符数量、是否满足某个条件等信息。
  3. 区间边界如何移动：判断移动一个边界后，区间状态是否仍然具有单调性或可以快速更新。

如果右边界不断向右移动时，区间状态可以增量计算，且不需要重复检查区间内部元素，就可以将暴力枚举优化为线性或接近线性的算法。

对于每个右边界 right，可以尝试维护满足条件的最小或最大左边界 left。如果窗口状态具有单调性，通常可以使用滑动窗口；如果数组中包含负数，区间和在移动边界后无法保持单调，就应该考虑前缀和、哈希表等方法。

很多子串问题还可以转化为前缀之间的关系。以子数组和为例，设 prefix[i] 表示前 i 个元素的和，则区间 [left, right) 的和为：

$$
prefix[right] - prefix[left]
$$

这样，寻找满足条件的连续区间，就可能转化为查找满足某种关系的两个前缀状态。

常见类型

  • 固定长度窗口：窗口长度固定为 k。右边界每向右移动一次，就移除左侧离开窗口的元素，并加入新的元素，适合计算长度为 k 的子数组或子串的和、最大值、平均值等。
  • 可变长度窗口：窗口长度根据条件动态变化。通常先移动右边界扩大窗口，再在窗口满足条件或出现冲突时移动左边界，适合寻找最长或最短的满足条件的子串，例如无重复字符的最长子串。
  • 字符频次窗口：使用集合、哈希表或数组维护窗口中的字符及出现次数，适合处理字符覆盖、异位词、重复字符和排列关系等问题。
  • 前缀和与哈希表：先计算前缀和，再利用两个前缀和的差表示区间和。当数组中可能包含负数、窗口和不具有单调性时，可以用哈希表记录前缀和及其出现次数，例如“和为 K 的子数组”。
  • 前缀信息与单调结构：当题目需要查询区间最值、且区间边界持续移动时，可以结合前缀最值、单调队列或单调栈，快速维护区间状态。
  • 字符串匹配：当问题是判断一个字符串是否包含另一个模式串，或查找模式串出现的位置时，可以使用暴力匹配、KMP、Rabin-Karp 等字符串匹配算法，减少重复比较。

相关 Python 知识点

双端队列 deque

Python 标准库 collections 提供了双端队列 deque（double-ended queue）。它支持在队列的左端和右端高效地添加、删除元素，适合实现普通队列、滑动窗口和单调队列。

1
2
3
4
5
6
7
8
9
10
from collections import deque

queue = deque()

queue.append(1)       # 右端添加：deque([1])
queue.append(2)       # 右端添加：deque([1, 2])
queue.appendleft(0)   # 左端添加：deque([0, 1, 2])

queue.pop()           # 右端删除，返回 2
queue.popleft()       # 左端删除，返回 0

常用操作如下：

操作 说明 复杂度
append(x) 在右端添加元素 $O(1)$
appendleft(x) 在左端添加元素 $O(1)$
pop() 删除并返回右端元素 $O(1)$
popleft() 删除并返回左端元素 $O(1)$
deque(iterable) 根据可迭代对象创建双端队列 $O(n)$

与列表相比，list.pop(0) 删除第一个元素时需要移动后面的所有元素，时间复杂度为 $O(n)$；deque.popleft() 不需要移动其他元素，时间复杂度为 $O(1)$。因此，需要频繁从左侧删除元素时，应优先使用 deque。

deque 也支持下标访问，但中间位置的访问效率不如列表，时间复杂度可能为 $O(n)$。如果只需要访问两端元素，应使用 append、appendleft、pop 和 popleft 等操作。

在滑动窗口中，可以使用 deque 保存窗口内的元素或下标；在单调队列中，还可以从队尾移除不可能成为答案的元素，从而在 $O(1)$ 时间内获取窗口最大值或最小值。

计数器 Counter

collections 还提供了 Counter，它是字典的一个子类，专门用于统计可哈希对象出现的次数。键表示元素，值表示该元素出现的次数，适合处理字符串或数组中的频次统计。

1
2
3
4
5
6
7
8
9
from collections import Counter

counter = Counter("abbccc")
print(counter)       # Counter({'c': 3, 'b': 2, 'a': 1})
print(counter['b'])  # 2

counter['a'] += 1
counter['c'] -= 1
del counter['b']

也可以直接根据一个可迭代对象创建计数器，或者使用字典初始化：

1
2
3
4
Counter([1, 2, 2, 3, 3, 3])
# Counter({3: 3, 2: 2, 1: 1})

Counter({'a': 2, 'b': 1})

常用操作如下：

操作 说明 复杂度
Counter(iterable) 统计可迭代对象中每个元素的次数 $O(n)$
counter[x] 查询元素 x 的计数，不存在时返回 0 平均 $O(1)$
counter[x] += 1 将元素 x 的计数加一 平均 $O(1)$
counter[x] -= 1 将元素 x 的计数减一 平均 $O(1)$
counter.most_common(k) 返回出现次数最多的前 k 个元素 与实现和 k 有关
counter1 == counter2 比较两个计数器中的元素频次 与元素种类数有关

在滑动窗口中，可以分别维护目标字符串和当前窗口的字符计数：右边界向右移动时增加字符，左边界向右移动时减少字符。当两个 Counter 相等时，说明两个字符串中每个字符的出现次数都相同，也就是它们是字母异位词。

1
2
3
4
5
6
7
from collections import Counter

target = Counter("abc")
window = Counter("bca")

if window == target:
    print("当前窗口是目标字符串的字母异位词")

需要注意，Counter 的值可以变成 0 或负数。如果希望计数器只保留正数计数，可以使用一元运算符 +：

1
2
counter = Counter({'a': 2, 'b': 0, 'c': -1})
print(+counter)  # Counter({'a': 2})

当只需要简单计数时，Counter 比手动使用 dict.get() 更简洁；当需要严格控制计数变化、频繁判断窗口是否满足条件时，也可以使用普通字典或定长数组，以便更明确地维护状态。

题目索引

题号 题目 难度
76 最小覆盖子串 困难
239 滑动窗口最大值 困难
560 和为 K 的子数组 中等

题目记录

最小覆盖子串

题号：76
难度：困难

题目描述

给定两个字符串 s 和 t，返回 s 中包含 t 所有字符（包括重复字符）的最短子串。如果不存在这样的子串，返回空字符串 ""。测试用例保证答案唯一。

示例

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释："BANC" 包含 A、B、C，且长度最短。

示例 2：

1
2
输入：s = "a", t = "a"
输出："a"

示例 3：

1
2
3
输入：s = "a", t = "aa"
输出：""
解释：s 中只有一个 a，无法满足 t 中两个 a 的要求。

提示

  • 1 <= s.length, t.length <= 10^5
  • s 和 t 由英文字母组成。
  • 进阶：设计时间复杂度为 $O(m+n)$ 的算法，其中 $m$、$n$ 分别是 s、t 的长度。

思路 $O(m+n)$

使用 Counter 统计 t 中每个字符需要的次数，记为 need；使用 window 维护当前窗口中字符的次数。valid 表示窗口内已有多少种字符的出现次数达到了 need 的要求。只有窗口中的字符属于 need 时才更新对应的计数。

右指针逐个加入 s 中的字符。当某个字符的窗口计数恰好达到需求时，valid 加一。若 valid == len(need)，说明当前窗口已经覆盖 t，此时不断右移左指针：每次先记录更短的有效窗口，再移除左侧字符；如果该字符移除前的计数恰好等于需求，移除后窗口就不再满足条件，valid 减一。

每个字符最多被左右指针各访问一次，因此时间复杂度为 $O(m+n)$；计数表最多保存英文字母对应的字符，空间复杂度为 $O(|\Sigma|)$，其中 $\Sigma$ 是字符集。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from collections import Counter, defaultdict


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        window = defaultdict(int)
        valid = 0
        left = 0
        best_start = 0
        best_len = float('inf')

        for right, char in enumerate(s):
            if char in need:
                window[char] += 1
                if window[char] == need[char]:
                    valid += 1

            while valid == len(need):
                length = right - left + 1
                if length < best_len:
                    best_len = length
                    best_start = left

                left_char = s[left]
                if left_char in need:
                    if window[left_char] == need[left_char]:
                        valid -= 1
                    window[left_char] -= 1
                left += 1

        return s[best_start:best_start + best_len] if best_len != float('inf') else ''

滑动窗口最大值

题号：239
难度：困难

题目描述

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

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

示例

示例 1：

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

示例 2：

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

提示

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

思路 $O(n)$

如果每个窗口都重新遍历其中的 k 个元素寻找最大值，时间复杂度为 $O(nk)$。可以使用单调队列优化这个过程。

单调队列使用 collections.deque 实现，队列中保存的是数组下标，而不是数组元素本身，并且保证队列从左到右对应的元素值递减：

1
nums[q[0]] >= nums[q[1]] >= nums[q[2]] >= ...

这样，队头下标 q[0] 对应的元素始终是当前窗口的最大值。

遍历数组时，使用 fast 表示当前加入窗口的元素下标，并按以下步骤维护队列：

  1. 如果队尾下标对应的元素小于 nums[fast]，那么这些元素即使还没有离开窗口，也不可能成为当前或后续窗口的最大值，将它们从队尾移除。
  2. 将 fast 加入队尾，保持队列的单调递减性质。
  3. 计算当前窗口的左边界 left = fast - k + 1，如果队头下标小于 left，说明队头已经离开窗口，将其从队头移除。
  4. 当窗口长度达到 k 后，队头元素就是当前窗口的最大值，将它加入结果数组。

每个下标最多入队一次、从队尾或队头出队一次，因此时间复杂度为 $O(n)$，空间复杂度为 $O(k)$。

这里虽然代码中有两个 while 循环，看起来可能需要在每轮遍历中重复处理很多元素，但不能简单地按照单轮最坏情况把它们相乘。应该从整个遍历过程统计每个下标的操作次数：

  • 每个数组下标只会被 queue.append 加入队列一次，因此入队操作总共是 n 次。
  • 一个下标从队列中移除后不会再次入队，因此每个下标最多只会被移除一次。它可能因为遇到更大的新元素而从队尾移除，也可能因为离开窗口而从队头移除，但不会被重复移除。
  • 每次入队、出队和下标访问都是 $O(1)$ 操作。

所以，所有循环中的入队和出队操作加起来最多只有常数倍的 n 次，总时间复杂度为 $O(n)$。这种把所有操作次数累计起来分析的方法称为摊还分析。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque
from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = deque()
        result = []

        for fast in range(len(nums)):
            # 移除不可能成为最大值的下标，维护单调递减队列
            while queue and nums[queue[-1]] < nums[fast]:
                queue.pop()

            queue.append(fast)

            # 计算当前窗口的左边界，并移除已经离开窗口的下标
            left = fast - k + 1
            while queue and queue[0] < left:
                queue.popleft()

            # 窗口长度达到 k 后，队头就是窗口最大值
            if left >= 0:
                result.append(nums[queue[0]])

        return result

和为 K 的子数组

题号：560
难度：中等

题目描述

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

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

示例

示例 1：

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

示例 2：

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

提示

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

思路 $O(n)$

这道题不能直接使用滑动窗口。滑动窗口通常要求窗口状态具有单调性，也就是移动指针后，窗口内的状态变化方向是可以预期的。

如果数组中的所有数字都是正数，当窗口内的和小于 k 时，可以向右移动右指针扩大窗口；当窗口内的和大于 k 时，可以移动左指针缩小窗口。但当数组中存在负数时，缩小窗口后，窗口和可能变小，也可能变大，因此无法根据当前窗口和决定应该移动哪个指针。

这道题可以使用前缀和来解决。设 prefix[i] 表示数组前 i 个元素的和，那么连续子数组 nums[left:right] 的和为：

$$
prefix[right] - prefix[left]
$$

如果子数组的和为 k，就有：

$$
prefix[left] = prefix[right] - k
$$

因此，遍历数组并计算当前前缀和时，只需要查询之前是否出现过前缀和 当前前缀和 - k。如果出现过，就说明存在对应的子数组，其和为 k。

使用哈希表记录每个前缀和出现的次数，而不是只记录是否出现过。因为相同的前缀和可能在不同位置出现多次，每一次出现都可能构成一个符合条件的子数组。

开始遍历前，将前缀和 0 加入哈希表一次，表示空数组的前缀和。这样可以正确处理从数组下标 0 开始的子数组。

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import defaultdict
from typing import List


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1

        prefix_sum = 0
        result = 0

        for num in nums:
            prefix_sum += num
            result += prefix_count[prefix_sum - k]
            prefix_count[prefix_sum] += 1

        return result
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 基本思路
  2. 2. 常见类型
  3. 3. 相关 Python 知识点
    1. 3.1. 双端队列 deque
    2. 3.2. 计数器 Counter
  4. 4. 题目索引
  5. 5. 题目记录
    1. 5.1. 最小覆盖子串
      1. 5.1.1. 题目描述
      2. 5.1.2. 示例
      3. 5.1.3. 提示
      4. 5.1.4. 思路 $O(m+n)$
      5. 5.1.5. 解法
    2. 5.2. 滑动窗口最大值
      1. 5.2.1. 题目描述
      2. 5.2.2. 示例
      3. 5.2.3. 提示
      4. 5.2.4. 思路 $O(n)$
      5. 5.2.5. 解法
    3. 5.3. 和为 K 的子数组
      1. 5.3.1. 题目描述
      2. 5.3.2. 示例
      3. 5.3.3. 提示
      4. 5.3.4. 思路 $O(n)$
      5. 5.3.5. 解法
  1. 1. 基本思路
  2. 2. 常见类型
  3. 3. 相关 Python 知识点
    1. 3.1. 双端队列 deque
    2. 3.2. 计数器 Counter
  4. 4. 题目索引
  5. 5. 题目记录
    1. 5.1. 最小覆盖子串
      1. 5.1.1. 题目描述
      2. 5.1.2. 示例
      3. 5.1.3. 提示
      4. 5.1.4. 思路 $O(m+n)$
      5. 5.1.5. 解法
    2. 5.2. 滑动窗口最大值
      1. 5.2.1. 题目描述
      2. 5.2.2. 示例
      3. 5.2.3. 提示
      4. 5.2.4. 思路 $O(n)$
      5. 5.2.5. 解法
    3. 5.3. 和为 K 的子数组
      1. 5.3.1. 题目描述
      2. 5.3.2. 示例
      3. 5.3.3. 提示
      4. 5.3.4. 思路 $O(n)$
      5. 5.3.5. 解法