560. 和为K的子数组
思路和解法
前缀和+哈希表
前缀和，就是把数组前面一段的和预处理出来，这样以后想求任意区间和时，就能很快算出来。还没取任何元素时，前缀和是 0。
本题通过两个前缀和相减得到k，即可找到目标结果。
定义哈希map，是为了快速记录“某个前缀和出现了多少次”，从而在遍历数组时，立刻判断有没有满足条件的子数组。
该题中哈希表的含义是：
key：某个前缀和的值
value：这个前缀和出现了多少次
整体思路：
通过按顺序取数组中元素，计算前缀和——初始化哈希map——遍历数组，寻找是否满足条件并更新
classSolution{public:intsubarraySum(vector<int>&nums,intk){unordered_map<int,int>map;map[0]=1;intcurrentSum=0;//前缀和记录intcount=0;//个数记录for(intnum:nums){currentSum=currentSum+num;if(map.find(currentSum-k)!=map.end()){count+=map[currentSum-k];}map[currentSum]++;}returncount;}};【注】
1、map[0]=1;没有元素时，前缀和是 0，因此map[0]=1
2、count+=map[currentSum-k];注意这里count不是+1，
因为 currentSum - k 可能之前出现过很多次。
ACM
#include<iostream>#include<unordered_map>#include<vector>usingnamespacestd;classSolution{public:intsubarraySum(vector<int>&nums,intk){unordered_map<int,int>map;map[0]=1;intcurrentSum=0;//前缀和记录intcount=0;//个数记录for(intnum:nums){currentSum=currentSum+num;if(map.find(currentSum-k)!=map.end()){count+=map[currentSum-k];}map[currentSum]++;}returncount;}};intmain(){intn,k;cin>>n>>k;vector<int>nums(n);for(inti=0;i<n;i++){cin>>nums[i];}Solution solution;cout<<solution.subarraySum(nums,k)<<endl;return0;}239. 滑动窗口最大值
本题是一道滑动窗口题目。窗口的特点就是：右边不断加入新元素，左边不断移出旧元素，这两个动作天然很像队列。
本题的难点是如何求一个区间里的最大值呢？构造单调队列！
如果直接使用普通队列（如 std::queue）来存储窗口内的元素，那么每次获取窗口最大值时，都需要遍历整个队列。
此时我们需要一个队列，这个队列放进窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列。
不要以为实现的单调队列就是对窗口里面的数进行排序，如果排序的话，那和优先级队列又有什么区别了呢。在单调队列中，我们通过一种淘汰策略来保证队列元素始终递减，而不是对整个窗口进行排序，队列首部即为最大值。
定义单调队列MyQueue类：
队首是最大元素！！！
pop(value)：当窗口移动时，需要移除离开窗口的元素。如果该元素恰好是当前队首（即最大值），则将其从队首弹出；否则，该元素早已在之前的 push 过程中被弹出，无需操作。
push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。这样保证了队列中元素从队首到队尾是递减的。
front()：直接返回队首元素，即当前窗口的最大值。
动画：
之前这里有疑问，后面想通了，因为目标就是获取当前窗口最大值，被淘汰的元素总是被更晚出现且更大的元素淘汰，因此当那个更大的元素离开窗口时，被淘汰的元素早已离开窗口（因为它的索引更小），所以不会出现遗漏。这样，队列始终维护一个递减序列，队首即为当前窗口最大值。
那么我们用什么数据结构来实现这个单调队列呢？
使用deque最为合适。
普通队列queue只支持在队尾入队、队首出队，无法在队尾进行弹出操作，因此无法维护单调性。而双端队列deque支持在两端高效地插入和删除（push_back、pop_back、push_front、pop_front）正好满足这两个需求，所以是最合适的数据结构。
整体思路：
1、定义类：
pop—pop的元素恰好与首部元素相同才pop
push—添加新元素时，只要队尾元素比新元素小，就把队尾弹出；直到队尾元素大于等于新元素，或者队列为空，再把新元素加入队尾。
front—返回队首元素
2、初始化窗口，得到初始结果，开始滑动
核心代码：
classSolution{private:classMyqueue{deque<int>deq;public:voidpop(intvalue){if(!deq.empty()&&value==deq.front()){deq.pop_front();}}voidpush(intvalue){//当新元素比队尾元素大时，队尾元素永远不可能成为后续窗口的最大值。//因为它比新元素小，而且比新元素更早离开窗口（索引更小），所以直接将其弹出。while(!deq.empty()&&value>deq.back()){deq.pop_back();}deq.push_back(value);}intfront(){returndeq.front();}};public:vector<int>maxSlidingWindow(vector<int>&nums,intk){Myqueue que;vector<int>result;//初始化第一个窗口for(inti=0;i<k;i++){que.push(nums[i]);}result.push_back(que.front());for(inti=k;i<nums.size();i++){que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}returnresult;}};ACM:
#include<iostream>#include<vector>#include<deque>usingnamespacestd;classSolution{private:classMyqueue{deque<int>deq;public:voidpop(intvalue){if(!deq.empty()&&value==deq.front()){deq.pop_front();}}voidpush(intvalue){while(!deq.empty()&&value>deq.back()){deq.pop_back();}deq.push_back(value);}intfront(){returndeq.front();}};public:vector<int>maxSlidingWindow(vector<int>&nums,intk){Myqueue que;vector<int>result;for(inti=0;i<k;i++){que.push(nums[i]);}result.push_back(que.front());for(inti=k;i<nums.size();i++){que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}returnresult;}};intmain(){intn,k;cin>>n>>k;vector<int>nums(n);for(inti=0;i<n;i++){cin>>nums[i];}Solution solution;vector<int>result=solution.maxSlidingWindow(nums,k);for(inti=0;i<result.size();i++){if(i>0)cout<<" ";cout<<result[i];}cout<<endl;return0;}【注】
1、第一个不输出空格，然后先输出空格，再输出元素，这样最后一个元素后面就没有空格了。
