Top100 子串
1.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
思路：
数据规模也蛮大；思考是不是用滑动窗口，因为是子串，不允许排序,所以用滑动窗口，不断往后移，暴力枚举遍历。
代码：
暴力没成功，当个反面例子，我先贴一会
class Solution(object):
def subarraySum(self, nums, k):
i,k=0,0
count=0
for i in range(len(nums)):
for j in range(i,len(nums)):
if sum(nums[i:j])==k :
print(i,j)
print(sum(nums[i:j]))
count+=1
return count换个思路：
使用前缀和的方法可以解决这个问题，因为我们需要找到和为k的连续子数组的个数。通过计算前缀和，我们可以将问题转化为求解两个前缀和之差等于k的情况。
假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j（i < j），如果prefixSum[j] - prefixSum[i] = k，即从第i个位置到第j个位置的元素之和等于k，那么说明从第i+1个位置到第j个位置的连续子数组的和为k。
通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。
这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。
每次的前缀和放入map哈希表中，哈希表的索引是pre，如果未出现过，则创建一个键值对。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto& x:nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;
}
return count;
}
};
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]提示：
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
思路：
1)先是暴力解法，就可以按照遍历的方式，从头到尾，以k为长度，然后寻找最大值放入答案的列表中。
2)稍微优化一点点，首先将前k个元素排序，然后进行遍历。遍历过程中需要判断：
是否大于最大值，如果是，则作为队首元素，队尾出队；如果小于最小值，则直接舍弃；如果处于中间，则队尾元素出队，该元素入队；结束后重新排序！（写到这自己都觉得蠢了，这叫优化？？）
3）使用双项队列。这里为了效率和快捷使用了 deque 容器，也可以使用 list 容器。
声明了一个变量 deque<int>window，用于存储下标。这个变量有以下 特点:
①变量的最前端（也就是 window.front()）是此次遍历的最大值的下标
②当我们遇到新的数时，将新的数和双项队列的末尾（也就是window.back()）比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才停止，做法有点像使用栈进行括号匹配。
③双项队列中的所有值都要在窗口范围内
特点一只是方便我们获取每次窗口滑动一格之后的最大值，我们可以直接通过 window.front() 获得。通过特点二，可以保证队列里的元素是从头到尾降序的，由于队列里只有窗口内的数，所以他们其实就是窗口内第一大，第二大，第三大... 的数。特点三就是根据题意设置的。但我们实际上只用比较现在的下标和 window.front() 就可以了，为什么呢？
因为只要窗口内第一大元素也就是这个 window.front() 在窗口内，那我们可以不用管第二大第三大元素在不在区间内了。因为答案一定是这个第一大元素。如果 window.front() 不在窗口内，则将其弹出，第二个大元素变成第一大元素，第三大元素变成第二大元素以此类推。
代码编写的过程还要时刻检查队列是否为空防止抛出异常，根据上面这些信息我们就可以编写此题的代码了。
代码：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(k==0)return {};
vector<int>res;
deque<size_t>window;
/*Init K integers in the list*/
for (size_t i = 0; i < k; i++) {
while (!window.empty() && nums[i] > nums[window.back()]) {
window.pop_back();
}
window.push_back(i);
}
res.push_back(nums[window.front()]);
/*End of initialization*/
for (size_t i = k; i < nums.size(); i++) {
if (!window.empty() && window.front() <= i - k) {
window.pop_front();
}
while (!window.empty() && nums[i] > nums[window.back()]) {
window.pop_back();
}
window.push_back(i);
res.push_back(nums[window.front()]);
}
return res;
}
};
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 的子串中， 因此没有符合条件的子字符串，返回空字符串。提示：
m == s.lengthn == t.length1 <= m, n <= 10^5s和t由英文字母组成
思路：
这个不会！直奔题解！
双指针，我们移动右指针同时统计可以匹配目标字符串的字符个数，当一个右指针可以匹配所有的目标字串时，我们更新左端点找到一个最短的子串。
代码：
class Solution {
public:
string minWindow(string s, string t) {
int n = s.size(), m = t.size();
vector<int> res(2, INT_MAX);
unordered_map<char, int> h;
unordered_map<char, int> hs;
for(auto e : t) hs[e]++;
int cnt = 0;
for(int i = 0, j = 0; i < n; i++)
{
h[s[i]]++;
if(hs.find(s[i]) != hs.end())
{
if(h[s[i]] == hs[s[i]]) cnt++; // 统计当前s中可以匹配t的字符个数
}
while(cnt == hs.size()) // 可以匹配所有字符时，说明我们找到了一个合法子串
{
// 尝试更新左端点找到一个最短的子串
h[s[j]]--;
if(hs.find(s[j]) != hs.end())
{
if(h[s[j]] < hs[s[j]]) // 左端点的字符更新后如果无法满足和t匹配更新答案和种类数
{
cnt--;
if(i - j + 1 < res[0])
{
res[0] = i - j + 1;
res[1] = j;
}
}
}
j++;
}
}
if(res[0] == INT_MAX) return ""; // 无法匹配当前的t字符串
return s.substr(res[1], res[0]);
}
};