文章

hot100子串题解

发表于 更新于
作者 匆匆那年 16 分钟阅读

560. 和为K的子数组

问题描述

给你一个整数数组 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$

题解

这个问题可以通过前缀和与哈希表的方法来高效解决。

解题思路

  1. 前缀和:
    • 用一个变量 prefixSum 来记录到当前元素的累积和。
    • 如果子数组的和为 k，则可以表示为 prefixSum[j] - prefixSum[i] = k，其中 j 是当前索引，i 是某个之前的索引。
  2. 哈希表:
    • 用哈希表记录每个前缀和出现的次数。
    • 遍历数组时，计算当前的 prefixSum，并检查是否存在 prefixSum - k 的值。如果存在，就说明有一个或多个子数组的和等于 k。
  3. 算法步骤:
    • 初始化一个哈希表 prefixCount，其中键是前缀和，值是该前缀和出现的次数。初始值为 {0: 1}，表示和为 0 的前缀和出现过一次（空数组）。
    • 遍历数组，计算 prefixSum，同时检查 prefixSum - k 是否存在于 prefixCount 中。如果存在，加上 prefixCount[prefixSum - k] 的值到结果中。
    • 更新 prefixCount，将当前 prefixSum 的计数加 1。

C++代码实现

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
33
34
35
36
37
38

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1; // 初始前缀和为0的次数为1

    int prefixSum = 0;
    int count = 0;

    for (int num : nums) {
        prefixSum += num;

        // 检查 prefixSum - k 是否存在
        if (prefixCount.find(prefixSum - k) != prefixCount.end()) {
            count += prefixCount[prefixSum - k];
        }

        // 更新 prefixCount
        prefixCount[prefixSum]++;
    }

    return count;
}

int main() {
    vector<int> nums = {1, 1, 1};
    int k = 2;
    cout << "结果: " << subarraySum(nums, k) << endl;

    nums = {1, 2, 3};
    k = 3;
    cout << "结果: " << subarraySum(nums, k) << endl;

    return 0;
}

复杂度分析

  • 时间复杂度: $O(n)$，其中 $n$ 是数组的长度。我们只需遍历数组一次，每次操作哈希表的复杂度为 $O(1)$。
  • 空间复杂度: $O(n)$，在最坏情况下，哈希表中可能存储所有不同的前缀和。

示例输出

1
2

结果: 2
结果: 2

这种方法高效且易于实现，非常适合解决和为 k 的子数组计数问题。

239. 滑动窗口最大值

问题描述

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11

输入：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：

1
2

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

提示：

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

题解

要解决滑动窗口最大值的问题，可以使用 双端队列（Deque），它能够高效地在 $O(n)$ 时间复杂度内解决此问题。

解题思路

  1. 双端队列维护滑动窗口：
    • 使用一个双端队列 deque，存储窗口中可能成为最大值的元素的索引。
    • 队列中元素按值递减顺序存储，队首始终是当前窗口的最大值索引。
  2. 具体操作：
    • 遍历数组的每个元素，维护一个大小为 $k$ 的窗口。
    • 移除队列中所有不在当前窗口范围内的元素（超出范围的索引）。
    • 如果当前元素大于队列中索引对应的值，则移除队列中所有比当前元素小的索引（它们不可能成为最大值）。
    • 将当前元素的索引加入队列。
    • 如果窗口的大小已经达到 $k$，将队列首部的值加入结果数组。
  3. 算法步骤：
    • 初始化一个双端队列 deque 和结果数组 result。
    • 遍历数组，维护双端队列。
    • 当遍历到的索引 $i$ 大于等于 $k - 1$ 时，将窗口的最大值加入结果数组。

C++代码实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // 存储窗口内可能成为最大值的索引
    vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        // 移除不在窗口范围内的索引
        if (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 移除比当前元素小的所有索引
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        // 将当前索引加入队列
        dq.push_back(i);

        // 当窗口大小达到 k 时，记录当前窗口的最大值
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    vector<int> result = maxSlidingWindow(nums, k);
    cout << "滑动窗口最大值: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

复杂度分析

  1. 时间复杂度:
    • 每个元素最多进队一次、出队一次，双端队列的操作复杂度为 $O(1)$。
    • 总时间复杂度为 $O(n)$。
  2. 空间复杂度:
    • 双端队列中最多存储 $k$ 个索引，因此空间复杂度为 $O(k)$。

示例输出

1

滑动窗口最大值: 3 3 5 5 6 7

优化提示

  • 本解法利用双端队列维护递减序列，在遍历时每个元素最多处理两次（一次进队，一次出队），因此非常高效。
  • 适用于大规模数据的场景，如 $n$ 达到 $10^5$。

76. 最小覆盖子串

问题描述

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

注意：

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

示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3:

1
2
3
4

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

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

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

题解

解决这个问题的关键是使用 滑动窗口 和 字符频率计数 方法，以实现线性时间复杂度 $O(m + n)$ 的算法。

解题思路

  1. 滑动窗口:
    • 使用两个指针 left 和 right 表示当前窗口。
    • 通过调整 right 扩大窗口，直到窗口包含了所有 t 的字符。
    • 然后通过调整 left 缩小窗口，去掉不必要的字符，直到窗口不再包含所有 t 的字符。
  2. 字符频率计数:
    • 使用两个数组 tFreq 和 windowFreq 分别记录字符串 t 中的字符频率以及当前窗口中字符的频率。
    • 如果当前窗口中所有字符的频率都大于等于 tFreq，则说明当前窗口满足条件。
  3. 算法步骤:
    • 初始化 tFreq 来记录字符串 t 中的字符频率。
    • 遍历字符串 s，动态更新窗口的字符频率，并判断窗口是否包含所有 t 的字符。
    • 当窗口包含所有字符时，尝试收缩窗口，记录当前最小窗口。
    • 最后返回最小窗口的子串。

C++代码实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;

string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";

    // 记录 t 中的字符频率
    unordered_map<char, int> tFreq;
    for (char c : t) {
        tFreq[c]++;
    }

    // 用于记录窗口中字符频率
    unordered_map<char, int> windowFreq;
    int left = 0, right = 0;
    int minLength = INT_MAX;
    int minStart = 0; // 记录最小窗口的起始位置
    int required = tFreq.size(); // t 中不同字符的数量
    int formed = 0; // 当前窗口中满足条件的字符数

    while (right < s.size()) {
        char c = s[right];
        windowFreq[c]++;

        // 如果当前字符的频率等于 t 中的频率，表示该字符满足条件
        if (tFreq.count(c) && windowFreq[c] == tFreq[c]) {
            formed++;
        }

        // 当窗口完全包含 t 中所有字符时，尝试缩小窗口
        while (formed == required) {
            // 更新最小窗口
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                minStart = left;
            }

            // 移除左边界字符
            char leftChar = s[left];
            windowFreq[leftChar]--;
            if (tFreq.count(leftChar) && windowFreq[leftChar] < tFreq[leftChar]) {
                formed--;
            }
            left++;
        }

        // 扩大右边界
        right++;
    }

    return minLength == INT_MAX ? "" : s.substr(minStart, minLength);
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";

    cout << "最小覆盖子串: " << minWindow(s, t) << endl;

    s = "a";
    t = "a";
    cout << "最小覆盖子串: " << minWindow(s, t) << endl;

    s = "a";
    t = "aa";
    cout << "最小覆盖子串: " << minWindow(s, t) << endl;

    return 0;
}

复杂度分析

  1. 时间复杂度:
    • 滑动窗口的左右指针各遍历整个字符串一次，总时间复杂度为 O(m+n)O(m + n)，其中 mm 是字符串 s 的长度，nn 是字符串 t 的长度。
  2. 空间复杂度:
    • 额外使用了两个哈希表存储字符频率，大小与字符集相关。若假设字符集固定为英文字母，空间复杂度为 O(1)O(1)。

示例输出

1
2
3

最小覆盖子串: BANC
最小覆盖子串: a
最小覆盖子串:

优化提示

  • 如果字符串 s 和 t 都是由 ASCII 字符构成，可以将哈希表替换为固定大小的数组来优化空间使用。
  • 双指针法与哈希表结合是解决类似覆盖子串问题的高效模板，适用于多种变体问题。
leetcode, hot100
C++ leetcode 子串
本文由作者按照 CC BY 4.0 进行授权