560. 和为 K 的子数组
给你一个整数数组
nums和一个整数k，请你统计并返回 该数组中和为k的子数组的个数 。子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2示例 2：
输入：nums = [1,2,3], k = 3 输出：2提示：
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
最容易想到的肯定是两个for循环枚举所有子数组（O(n^2)），但是试一下会发现超时了。
我想到了前缀和可以用来数组区间和的计算，但是没做出来看的题解，采取前缀和+哈希可以把时间复杂度优化到O(n)。思想就是：
通过sum统计前缀和，并通过哈希表进行计数统计。当sumPrefix[i] - sumPrefix[j] = 区间i到j的和 = k
时（前缀数组的定义），每有一个前缀和的值 = sum - k就会有一个区间也就是子数组的和等于k。
int subarraySum(vector<int>& nums, int k) {
int ans = 0;
int sum = 0;
unordered_map<int, int> hash;
hash[0] = 1;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (hash.count(sum - k))
ans += hash[sum - k];
hash[sum]++;
}
return ans;
}
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]提示：
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
优先队列
优先队列存储pair<int, int>，分别存储数组的值和下标，数组的值用来比较构建优先级队列，当最大值不在滑动窗口区间里时，下标用来出队列。
pair<T1, T2>的默认排序是先比较T1，T1相等时比较T2。用在这题上十分适用。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
priority_queue<pair<int, int>> q;
for (int i = 0; i < k; ++i)
q.emplace(nums[i], i);
ans.push_back(q.top().first);
for (int i = k; i < nums.size(); ++i) {
q.emplace(nums[i], i);
while (q.top().second < i - k + 1)
q.pop();
ans.push_back(q.top().first);
}
return ans;
}
单调队列
将每个数组的值都加入双向队列之前，每当nums[i] >= nums[q.back()]时，也就是nums[i]大于双向队列最后的元素，将其出队。由此可以保持双向队列单调递减，且最左端一定是区间最大值。并且每次判断双向队列最左端不在滑动窗口区间里时，不断出队列。
下面是题解的图
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
deque<int> q; // 存数组下标
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()])
q.pop_back();
q.push_back(i);
}
ans.push_back(nums[q.front()]);
for (int i = k; i < nums.size(); ++i) {
while (!q.empty() && nums[i] >= nums[q.back()])
q.pop_back();
q.push_back(i);
while (q.front() < i - k + 1)
q.pop_front();
ans.push_back(nums[q.front()]);
}
return ans;
}
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 的子串中， 因此没有符合条件的子字符串，返回空字符串。提示：
m == s.lengthn == t.length1 <= m, n <= 10^5s和t由英文字母组成
count是这题的关键，哈希表确定是否是t中同样的字符来更新count当count == t.size()时，s是t的覆盖子串。通过滑动窗口来不断确定最小长度(minlen)和起始位置(begin)，即可确定最小覆盖子串。
string minWindow(string s, string t) {
// 滑动窗口+哈希
int hash_s[128] = {0}, hash_t[128] = {0};
for (auto ch : t)
hash_t[ch]++;
int left = 0, right = 0;
int minlen = INT_MAX, begin = -1;
int count = 0;
while (right < s.size()) {
int chr = s[right];
hash_s[chr]++;
if (hash_s[chr] <= hash_t[chr])
count++;
while (count == t.size()) {
int chl = s[left];
if (minlen > right - left + 1) {
minlen = right - left + 1;
begin = left;
}
if (hash_s[chl] <= hash_t[chl])
count--;
hash_s[chl]--;
left++;
}
right++;
}
return (begin == -1 ? "" : s.substr(begin, minlen));
}