Leetcode Hot 100 —— 子串

560. 和为K的子数组思路和解法前缀和哈希表前缀和就是把数组前面一段的和预处理出来这样以后想求任意区间和时就能很快算出来。还没取任何元素时前缀和是 0。本题通过两个前缀和相减得到k即可找到目标结果。定义哈希map是为了快速记录“某个前缀和出现了多少次”从而在遍历数组时立刻判断有没有满足条件的子数组。该题中哈希表的含义是key某个前缀和的值value这个前缀和出现了多少次整体思路通过按顺序取数组中元素计算前缀和——初始化哈希map——遍历数组寻找是否满足条件并更新classSolution{public:intsubarraySum(vectorintnums,intk){unordered_mapint,intmap;map[0]1;intcurrentSum0;//前缀和记录intcount0;//个数记录for(intnum:nums){currentSumcurrentSumnum;if(map.find(currentSum-k)!map.end()){countmap[currentSum-k];}map[currentSum];}returncount;}};【注】1、map[0]1;没有元素时前缀和是 0因此map[0]12、countmap[currentSum-k];注意这里count不是1因为 currentSum - k 可能之前出现过很多次。ACM#includeiostream#includeunordered_map#includevectorusingnamespacestd;classSolution{public:intsubarraySum(vectorintnums,intk){unordered_mapint,intmap;map[0]1;intcurrentSum0;//前缀和记录intcount0;//个数记录for(intnum:nums){currentSumcurrentSumnum;if(map.find(currentSum-k)!map.end()){countmap[currentSum-k];}map[currentSum];}returncount;}};intmain(){intn,k;cinnk;vectorintnums(n);for(inti0;in;i){cinnums[i];}Solution solution;coutsolution.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的元素恰好与首部元素相同才poppush—添加新元素时只要队尾元素比新元素小就把队尾弹出直到队尾元素大于等于新元素或者队列为空再把新元素加入队尾。front—返回队首元素2、初始化窗口得到初始结果开始滑动核心代码classSolution{private:classMyqueue{dequeintdeq;public:voidpop(intvalue){if(!deq.empty()valuedeq.front()){deq.pop_front();}}voidpush(intvalue){//当新元素比队尾元素大时队尾元素永远不可能成为后续窗口的最大值。//因为它比新元素小而且比新元素更早离开窗口索引更小所以直接将其弹出。while(!deq.empty()valuedeq.back()){deq.pop_back();}deq.push_back(value);}intfront(){returndeq.front();}};public:vectorintmaxSlidingWindow(vectorintnums,intk){Myqueue que;vectorintresult;//初始化第一个窗口for(inti0;ik;i){que.push(nums[i]);}result.push_back(que.front());for(intik;inums.size();i){que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}returnresult;}};ACM:#includeiostream#includevector#includedequeusingnamespacestd;classSolution{private:classMyqueue{dequeintdeq;public:voidpop(intvalue){if(!deq.empty()valuedeq.front()){deq.pop_front();}}voidpush(intvalue){while(!deq.empty()valuedeq.back()){deq.pop_back();}deq.push_back(value);}intfront(){returndeq.front();}};public:vectorintmaxSlidingWindow(vectorintnums,intk){Myqueue que;vectorintresult;for(inti0;ik;i){que.push(nums[i]);}result.push_back(que.front());for(intik;inums.size();i){que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}returnresult;}};intmain(){intn,k;cinnk;vectorintnums(n);for(inti0;in;i){cinnums[i];}Solution solution;vectorintresultsolution.maxSlidingWindow(nums,k);for(inti0;iresult.size();i){if(i0)cout ;coutresult[i];}coutendl;return0;}【注】1、第一个不输出空格然后先输出空格再输出元素这样最后一个元素后面就没有空格了。