目录

1  560. 和为 K 的子数组

2  239. 滑动窗口最大值

3  76. 最小覆盖子串

---

菜鸟做题第二周，语言是 C++

1  560. 和为 K 的子数组

题眼：“子数组是数组中元素的连续非空序列。”

解决本问题的关键就在于如何翻译问题。子数组 s 的和可以看作数组 i 的和减去数组 j 的和，这样就把 “求子数组的和” 转换为了 “前缀和之间的差”。如下图所示：

解题思路：

1. 遍历数组，计算所有前缀和 sum(i)，并存入哈希表中
2. 同时查看哈希表中是否存在前缀和 sum(j) 等于 sum(i) - k

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> hash;int pre = 0, ans = 0;for (auto num:nums) {pre += num;if (pre == k) ++ans;if (hash.find(pre - k) != hash.end()) {ans += hash[pre - k];}++hash[pre];}return ans;}
};

说明：这句代码是为了避免遗漏本身前缀和就等于 k 的情况

if (pre == k) ++ans;

官方题解一开始就给哈希表插入了 (0, 1)，应该就是为了解决这个问题，但我没有照做。

2  239. 滑动窗口最大值

主要看你会不会优先队列。。。

解题思路：

1. 初始化：插入前 k 个数字，队列头就是最大值
2. 一格一格地右移窗口，并弹出队列头
3. 若队列头的下标处在窗口内，则它就是窗口内的最大值
4. 若队列头的下标处在窗口外，则继续弹出，直到处在窗口内

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();priority_queue<pair<int, int>> q;for (int i = 0; i < k; ++i) {q.emplace(nums[i], i);}vector<int> ans = {q.top().first};for (int i = k; i < n; ++i) {q.emplace(nums[i], i);while (q.top().second <= i - k) {q.pop();}ans.push_back(q.top().first);}return ans;}
};

3  76. 最小覆盖子串

读懂题意很重要。。。

题目只要求当前窗口内的字母能够拼出字符串 t 即可，没有要求字母数量要一致。因此，判断能否覆盖的方法如下：

bool succeed() {for (auto t:tCount) {if (sCount[t.first] < t.second) {return false;}}return true;
}

其中，tCount 和 sCount 均为哈希表。tCount 记录的是 t 的字母数量，sCount 记录的是 s 的字母数量。这里只要求 sCount 中相应字母的数量比 t 的多即可，而不一定要相等。

解题思路：

1. 首先移动右指针 right 使得窗口能够覆盖子串
2. 然后移动左指针 left 直到窗口刚好不能覆盖子串
3. 再移动右指针 right 使得窗口能够覆盖子串
4. 循环往复（期间要维护最小长度和起始位置）

思路说明图：

可以类比为一只爬行的毛毛虫。首先，毛毛虫伸头，使得窗口能够覆盖子串 “ABC”；然后，毛毛虫收尾，使得窗口刚好不能覆盖子串 “ABC”；毛毛虫再伸头，使得窗口能够再次覆盖子串 “ABC”；以此类推。

class Solution {
public:unordered_map<char, int> sCount, tCount;bool succeed() {for (auto t:tCount) {if (sCount[t.first] < t.second) {return false;}}return true;}string minWindow(string s, string t) {int sLen = s.size(), tLen = t.size();int minStart = 0, minLen = sLen;string ans;int flag = 0;if (sLen < tLen) return "";for (int i = 0; i < tLen; ++i) {++tCount[t[i]];}int left = 0, right = 0;while (right < sLen) {// 毛毛虫伸头if (tCount.find(s[right]) != tCount.end()) {++sCount[s[right]];}++right;// 毛毛虫收尾while (succeed()) {flag = 1;if (tCount.find(s[left]) != tCount.end()) {--sCount[s[left]];}if (minLen > right - left) {minLen = right - left;minStart = left;}++left;}}// 处理结果if (flag) {for (int i = minStart; i < minStart + minLen; ++i) {ans.push_back(s[i]);}}return ans;}
};

说明：每次做如下判断是因为我们只关心子串中含有的字母的个数

if (tCount.find(s[right]) != tCount.end()) {++sCount[s[right]];
}