leetcode（hot100）10、11、12

解题思路：前缀和与哈希表  因为本题数组的值不是全部都是正整数，所以不能用滑动窗口 

这道题哈希表所采用的思想和两数之和用相同的方法 前缀和就相当于两数之和的和 然后从哈希表中去寻找sum-k的值 找到的值就是结果，首先将哈希表的键置0值置为1因为如果sum-k刚好等于0那这个时候怎么办

class Solution {
public:
//前缀和加上哈希表
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0, result = 0;
        unordered_map<int,int>map{{0,1}};
        for(int i = 0;i<nums.size();i++){
            sum += nums[i];
            if(map.find(sum-k) != map.end()){
                result += map[sum-k];
            }
            map[sum]++;
        }
        return result;
    }
};

解题思路：使用一个双端队列deque

首先想一想滑动窗口的大概思路，然后按照滑动窗口的框架来写 dp中主要存储的是下标，保持队列单调递减，当加入的值小于dp中的值时用pop_back,

当dp中的下标窗口超了就pop_front(), 当窗口达到k记录最大值。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int left = 0;
        vector<int>result;
        deque<int>dp;//dp存储的是下标
        for(int right = 0;right < nums.size();right++){
            if(!dp.empty() && dp.front() == right-k){//移除超出窗口的元素
                dp.pop_front();
            }
            while(!dp.empty() && nums[dp.back()] < nums[right]){//保持队列单调递减
                dp.pop_back();
            }
            dp.push_back(right);
            
            if(right >= k-1){//当窗口达到k时记录最大值
                result.push_back(nums[dp.front()]);
            }
        }
        return result;
    }
};

解题思路：滑动窗口  

右指针遍历整个字符串 s 如果当前字符的频率满足 t 中的频率，增加 valid 

当 valid == cont.size() 时，窗口包含了 t 中所有的字符，开始尝试收缩窗口

更新最小窗口长度和起始位置 收缩窗口，移动左指针 如果某个字符的频率不再满足 t 中的要求，减少 valid

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> conts;  // 当前窗口的字符频率
        unordered_map<char, int> cont;   // t 中字符的频率

        // 记录 t 中每个字符的频率
        for (char c : t) {
            cont[c]++;
        }

        int left = 0, valid = 0, start = 0, minlen = INT_MAX;
        
        // 右指针遍历整个字符串 s
        for (int right = 0; right < s.size(); right++) {
            // 如果 s[right] 在 t 中
            if (cont.count(s[right])) {
                conts[s[right]]++;
                // 如果当前字符的频率满足 t 中的频率，增加 valid
                if (conts[s[right]] == cont[s[right]]) {
                    valid++;
                }
            }

            // 当 valid == cont.size() 时，窗口包含了 t 中所有的字符，开始尝试收缩窗口
            while (valid == cont.size()) {
                // 更新最小窗口长度和起始位置
                if (right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    start = left;
                }

                // 收缩窗口，移动左指针
                if (cont.count(s[left])) {
                    conts[s[left]]--;
                    // 如果某个字符的频率不再满足 t 中的要求，减少 valid
                    if (conts[s[left]] < cont[s[left]]) {
                        valid--;
                    }
                }
                left++;  // 左指针右移，收缩窗口
            }
        }

        // 如果找到了符合条件的最小窗口，则返回，否则返回空字符串
        return minlen == INT_MAX ? "" : s.substr(start, minlen);
    }
};