4. 子串

约 1503 字大约 5 分钟

LeetcodePythonC++

2025-09-08

4. 子串

4.1 和为 K 的子数组

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

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

提示

思路：先转化为前缀和的思路，再转化为两数之和，灵神的思路太妙了，建议多看几遍灵神的题解。先得到前缀和，再拿前缀和做两数之和。

Python

class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
    s = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        s[i + 1] = s[i] + x
    res = 0
    cnt = defaultdict(int)
    for sj in s:
        res += cnt[sj - k]
        cnt[sj] += 1
    return res

C++

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int> pre_sum;
        int res = 0;
        pre_sum.resize(nums.size() + 1);
        for (int i = 0; i < nums.size(); i++) {
            pre_sum[i + 1] = pre_sum[i] + nums[i];
        }
        unordered_map<int, int> cnt;
        for (int x : pre_sum) {
            res += cnt.contains(x - k) ? cnt[x - k] : 0;
            cnt[x]++;
        }
        return res;
    }
};

时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。

空间复杂度： $O(n)$ 。

4.2 滑动窗口最大值

239. 滑动窗口最大值
给你一个整数数组 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]
提示
思路：单调栈。用一个双端队列构造一个从大到小的单调栈，无非是入和出的逻辑，如果当前元素比队尾元素大，那么不符合单调栈，队尾元素出列（右端），直到符合才入栈；如果队头元素超过了k大小的窗口，需要及时出列（左端）；每一轮循环栈内最大元素（左端）就是当前窗口的最大值。
Python
```
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    from collections import deque
    q = deque()
    res = []
    for i, num in enumerate(nums):
        while q and num > nums[q[-1]]:
            q.pop()
        q.append(i)
        left = i - k + 1
        if left > q[0]:
            q.popleft()
        if left >= 0:
            res.append(nums[q[0]])
    return res
```
C++
```
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        vector<int> res(n - k + 1);
        for (int i = 0; i < n; i++) {
            while (!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            int left = i - k + 1;
            if (left > q.front()) {
                q.pop_front();
            }
            if (left >= 0) {
                res[left] = nums[q.front()];
            }
        }
        return res;
    }
};
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。由于每个下标至多入队出队各一次，所以二重循环的循环次数是 O(n) 的。
空间复杂度： $O(min(k,U))$ ，其中 U 是 nums 中的不同元素个数（本题至多为 20001）。双端队列至多有 k 个元素，同时又没有重复元素，所以也至多有 U 个元素，所以空间复杂度为 $O(min(k,U))$ 。返回值的空间不计入。

4.3 最小覆盖子串

76. 最小覆盖子串
给你一个字符串 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的计数器录入s的一个字符，如果s的计数器涵盖（看示例 1，s 的子串 BANC 中每个字母的出现次数，都大于等于 t=ABC 中每个字母的出现次数，这就叫涵盖。）t的计数器，那么表明覆盖了，如果当前左右指针长度比答案指针短，就更新。
Python
```
class Solution:
def minWindow(self, s: str, t: str) -> str:
    cnt_s = Counter()
    cnt_t = Counter(t)
    res_left = -1, res_right = len(s)
    left = 0
    for right, c in enumerate(s):
        cnt_s[c] += 1
        while cnt_s >= cnt_t:
            if right - left < res_right - res_left:
                res_left, res_right = left, right
            cnt_s[s[left]] -= 1
            left += 1
    return "" if res_left < 0 else s[res_left : res_right + 1]
```
C++
时间复杂度： $O(∣Σ∣m+n)$ ，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣ 为字符集合的大小，本题字符均为英文字母，所以 ∣Σ∣=52。注意 left 只会增加不会减少，left 每增加一次，我们就花费 $O(∣Σ∣)$ 的时间。因为 left 至多增加 m 次，所以二重循环的时间复杂度为 $O(∣Σ∣m)$ ，再算上统计 t 字母出现次数的时间 $O(n)$ ，总的时间复杂度为 $O(∣Σ∣m+n)$ 。
空间复杂度： $O(∣Σ∣)$ 。如果创建了大小为 128 的数组，则 ∣Σ∣=128。