和为 K 的子数组

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

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

不能用滑动窗口，因为有负数，窗口不是单调扩张/收缩的。

tag 里有前缀和，先起一个数组把前缀和计算出来。怎么找数组呢，以每一个 index 为开头向后探一遍？这个是 O(N2)O(N^2)，大抵是慢了的。

这个场景比较像两数之和，只不过查找的目标变成了找符合固定两数之差的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixCount;
        prefixCount[0] = 1;
        int sum = 0, count = 0;
        for (int num : nums) {
            sum += num;
            int target = sum - k;
            if (prefixCount.find(target) != prefixCount.end()) {
                count += prefixCount[target];
            }
            prefixCount[sum]++;
        }
        return count;
    }
};

滑动窗口最大值

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

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

我写困难，真的假的？

暴力过不去，时间复杂度O(nk)O(nk)了。提示用双端队列 deque。

维护一个双端队列 deque，存储可能成为窗口最大值的元素下标，队列内下标对应的值严格递减。

  • 每次窗口右移，新元素 nums[i] 入队：将队列中所有小于 nums[i] 的元素下标弹出（它们已不可能成为之后窗口的最大值），然后将 i 加入队尾。
  • 如果队首下标已滑出窗口（队首下标 <= i - k），则弹出队首。
  • 当前窗口最大值就是队首元素对应的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;

        for (int i = 0; i < nums.size(); ++i) {
            if (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }
            dq.push_back(i);
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        return result;
    }
};

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

步骤 下标 i 窗口内容 当前队列(下标) 队列对应值 最大值 说明
初始 0 [1] [0] [1] -
1 [1,3] 弹出0后[1] [3] - 1<3，1被淘汰
形成窗口 2 [1,3,-1] [1,2] [3,-1] 3
滑动 3 [3,-1,-3] 弹出1? 1仍合法 → [1,2,3] → 维护递减：-3入队前不弹任何，所以[1,2,3] [3,-1,-3] 3 队首1未滑出
4 [-1,-3,5] 检查队首1滑出 → 弹出1 → [2,3]；5入队前弹出所有小于5的：2(-1)和3(-3)被弹 → [4] [5] 5
5 [-3,5,3] [4,5] [5,3] 5
6 [5,3,6] 队首4未滑出；6入队前弹5(3<6) → 队尾变为4 → 弹4(5<6) → [6] [6] 6
7 [3,6,7] 检查队首6滑出？6>4合法；7入队弹6(6<7) → [7] [7] 7

结果：[3,3,5,5,6,7]。

最小覆盖子串

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

测试用例保证答案唯一。

你们子串都那么变态吗…

想起来 ADS 的 KMP 了，感觉这个难得多啊…

滑动窗口？无序集合？无序集合不行，因为可能有重复元素。那就和之前一样开计数数组。用 need 记录每个字符的目标次数，window 记录当前实际次数。valid 记录种类满足情况，不是总字符数。当所有种类都满足时，窗口一定包含 t 所有字符（含重复）。找到满足窗口后，立即收缩左边界，是为了寻找更短的满足窗口。左右指针各走一遍，O(m)O(m) 时间，O(1)O(1) 额外空间（固定 128）。

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
class Solution {
public:
    string minWindow(string s, string t) {
        int need[128] = {0};
        int window[128] = {0};
        int uniqueChars = 0;          // t 中不同字符种类数
        for (char c : t) {
            if (need[c] == 0) uniqueChars++;
            need[c]++;
        }

        int left = 0, right = 0;
        int valid = 0;
        int start = 0, minLen = INT_MAX;

        while (right < s.size()) {
            char c = s[right];
            right++;
            // 如果这个字符是需要的，达到要求的字符位数加 1
            if (need[c] > 0) {
                window[c]++;
                if (window[c] == need[c]) { // 超出不计
                    valid++;
                }
            }

            // 当窗口完全覆盖 t 时，尝试收缩 left
            while (valid == uniqueChars) { // 每一位的数量都是正确的
                // 更新答案
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                char d = s[left];
                left++;
                if (need[d] > 0) {
                    if (window[d] == need[d]) {
                        valid--;
                    }
                    window[d]--
                }
            }
        }

        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

有思路但是不会写…😭AI 怎么那么坏…