560.和为K的子数组
题目
我的思路：暴力
但是边界的问题一直有bug
class Solution {
public:int subarraySum(vector<int>& nums, int k) {int res=0;for(int i=0;i<nums.size();i++){int sum=nums[i];if(sum==k){res++;// continue;}for(int j=i+1;j<nums.size();j++){sum+=nums[j];if(sum==k){res++; }} }return res;}
};
别人的题解
题解
方法一：暴力枚举思路：
- 三重循环：
一层循环枚举做指针left，一层循环枚举right指针，最内层循环遍历left到right之间的连续字串，看是否和为k。 - 两重循环（和我的思路一样，精简了，但是超时了）
class Solution {
public:int subarraySum(vector<int>& nums, int k) {int res=0;for(int i=0;i<nums.size();i++){/* int sum=nums[i];if(sum==k){res++;}*/int sum=0;for(int j=i;j<nums.size();j++)//这里直接将j=i+1改成j=i,把sum每次都从0开始{sum+=nums[j];if(sum==k){res++; }} }return res;}};
官方的：看[j…i]是否和为k
class Solution {
public:int subarraySum(vector<int>& nums, int k) {int res=0;for(int i=0;i<nums.size();i++){ int sum=0;for(int j=i;j>=0;j--)//[j...i]是否满足和为k{ sum+=nums[j];if(sum==k){res++; }} }return res;}
};
方法二：前缀和+哈希
本质优化上面的，pre[i]为[0…i]的前缀和，计算[j…i]的和为公式：pre[i]-pre[j-1]==k,即pre[j-1]=pre[i]-k；
我们遍历的时候从左向右进行，使用i进行遍历，用哈希unordered_map<int,int> mp；存储<前缀和’‘i-k’‘，前缀和’‘i-k’'出现的次数>，即看是否有pre[j]存在，存在的话说明存在[j…i]的子数组。
【评论区补充】：
前缀和的概念 首先，我们使用一个叫做“前缀和”的概念。对于数组中的任何位置 j，前缀和 pre[j] 是数组中从第一个元素到第 j 个元素的总和。这意味着如果你想知道从元素 i+1 到 j 的子数组的和，你可以用 pre[j] - pre[i] 来计算。
使用 Map 来存储前缀和 在代码中，我们用一个 Map（哈希表）来存储每个前缀和出现的次数。这是为了快速检查某个特定的前缀和是否已经存在，以及它出现了多少次。
核心逻辑解析 当我们在数组中向前移动时，我们逐步增加 pre（当前的累积和）。对于每个新的 pre 值，我们检查 pre - k 是否在 Map 中。
class Solution {
public:int subarraySum(vector<int>& nums, int k) {int res=0,pre=0;unordered_map<int,int> mp;mp[0]=1; //刚开始第一个前缀出现的次数为1for(int i=0;i<nums.size();i++){ pre+=nums[i]; if(mp.find(pre-k)!=mp.end()){res+=mp[pre-k];}mp[pre]++; //先查询后再将当前pre存储}return res;}
};
239. 滑动窗口最大值
题目
这个题目和上面的题目有点类似，都是三重循环，一层是总的遍历数量，一层left，一层right遍历left到right之间的（k长度）
方法一：暴力超时了
方法二：优先队列。
对方法一的内层循环降低复杂度，其实通过priority_queue这个数据结构来找最大值，双指针还是两重循环，只是优先队列底层是堆，复杂度是O（logn）
方法三：单调队列
双指针i，j也可以是双端队列，左边i，右边j。单调队列用双端队列来实现。在二的基础上又降低了一层复杂度。
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {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);}vector<int> res={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){q.pop_front();}res.push_back(nums[q.front()]);} return res;}
};
76. 最小覆盖字串
题目
没有思路，不知道怎么判断滑动窗口里的字串字母个数是否小于等于t里的字母个数
这里官方用的哈希unordered_map，没有用vector v(26)
下面的评论区的解：FearnDreams看懂了：
- 使用一个单独的函数检查是否滑动窗口里的和s里的个数大于等于
- 检查的时机：当滑动窗口里新加入的字符在t里的时候就检查
- 注意使用s.substr(startpos,len);来截取，而不是用一个res变量保存每次最小的，所以用了res_left来保存每次滑动窗口最左边的位置。
class Solution {
public://定义两个哈希表，tstr用来存放t中元素的出现次数信息，sstr用来存放滑动窗口中元素的出现次数信息unordered_map<char,int> tstr,sstr;//检查当前的窗口是否是合格的窗口，即：//检查当前滑动窗口中元素是否完全覆盖了字符串t中的所有元素（重点是某元素的出现次数必须不小于t中对应元素的出现次数）bool check(){for(auto tchar : tstr){if(tchar.second > sstr[tchar.first]) return false;//注意这里的判断条件是大于//只要sstr中元素的second值不小于tchar中对应元素的second值就行}return true;}string minWindow(string s, string t) {int n1 = s.size(),n2 = t.size();if(n1<n2) return "";//如果t串比s串还长，s中肯定不能找到相应的子串int len = INT_MAX;//最小窗口的长度int ans_left = -1;//最小窗口的左边界指针//构造哈希表for(auto tchar : t)++tstr[tchar];int left = 0,right = 0;//窗口的左右两端指针//滑动窗口右端指针遍历整个s串for(int right = 0;right<n1;right++){ //每遍历一个元素，更新sstr中的元素信息++sstr[s[right]];//如果当前遍历到的元素在tstr中也有，说明此次遍历的更新是有效的更新，否则不用管，直接继续遍历if(tstr.find(s[right]) != tstr.end()){ //对于每一次有效的更新，检查当前窗口中的子串是否是一个合格的子串while(check() && left<=right){//如果当前子串是合格的，那么判断是否是最小的窗口if(len > right - left +1){//如果是最小的窗口，那么更新窗口信息ans_left = left;len = right - left + 1;}//当前子串如果是合格的，那么尝试移进窗口的左边界缩短窗口的长度--sstr[s[left]];//窗口左边界的元素信息从哈希表sstr中删除left++;//移进窗口左边界//移进之后，继续while判断移进后的子串是否是合格的，如果是合格的，继续重复同样的操作，更新窗口的信息}//一旦窗口不合格，窗口右边界的指针就继续往后遍历，拓宽窗口的长度}}if(ans_left == -1) return "";else return s.substr(ans_left,len);}
};
