【算法专题】滑动窗口

		class Solution {
		public:
		    int minSubArrayLen(int target, vector<int>& nums) 
		    {
		        int left = 0,right = 0,sum = 0,ans = INT_MAX;
		        while(right < nums.size())
		        {
		            // 进窗口
		            sum += nums[right];
		
		            // 满足条件就更新结果
		            while(sum >= target)
		            {
		                ans = min(ans, right - left + 1);
		
		                // 出窗口
		                sum -= nums[left];
		                left++;
		            }
		            right++;
		        }
		        return ans == INT_MAX? 0 : ans;
		    }
		};

		class Solution {
		public:
		    int lengthOfLongestSubstring(string s)
		    {
		        if (s.size() == 0) return 0;
		
		        int hash[128] = { 0 };
		
		        int ans = INT_MIN;
		        for (int left = 0, right = 0; right < s.size(); right++)
		        {
		            // 进窗口
		            hash[s[right]]++;
		
		            // 出窗口
		            while (hash[s[right]] > 1)
		            {
		                hash[s[left]]--;
		                left++;
		            }
		
		            // 出窗口后取值
		            ans = max(right - left + 1, ans);
		        }
		        return ans;
		    }
		};

		class Solution {
		public:
		    int longestOnes(vector<int>& nums, int k) 
		    {
		        int ans = 0, tmp = k;
		        for(int left = 0,right = 0;right < nums.size();right++)
		        {
		            // 有一个 0 进窗口 k 就减一
		            if(nums[right] == 0 && k >= 0)
		            {
		                k--;
		            }
		            
		            // 窗口内超过 k 个 0，出窗口并更新 k
		            while(nums[right] == 0 && k < 0)
		            {
		                if(nums[left] == 0)
		                    ++k;
		
		                left++;
		            }
		            ans = max(ans, right - left + 1);
		        }
		        return ans;
		    }
		};

		class Solution {
		public:
		    int minOperations(vector<int>& nums, int x)
		    {
		        int ans = INT_MIN, sum = 0;
		
		        // 转换为求和为 sum(nums)-x 的最长子数组问题
		        for (int i = 0; i < nums.size(); i++) sum += nums[i];
		
		        int target = sum - x, slipSum = 0;
		        if (target < 0) return -1;
		
		        // 操作窗口
		        for (int left = 0, right = 0; right < nums.size(); right++)
		        {
		            // 进窗口
		            slipSum += nums[right];
		
		            // 出窗口
		            while (slipSum > target)
		            {
		                slipSum -= nums[left];
		                left++;
		            }
		
		            // 更新数据
		            if (slipSum == target)
		                ans = max(ans, right - left + 1);
		        }
		
		        return ans == INT_MIN ? -1 : nums.size() - ans;
		    }
		};

		class Solution {
		public:
		    int totalFruit(vector<int>& fruits) 
		    {
		        int ans = 0;
		        unordered_map<int, int> hash;
		
		        for(int left = 0,right = 0;right < fruits.size();right++)
		        {
		            // 进窗口
		            hash[fruits[right]]++;
		
		            // 超过两个种类的水果，就出窗口，并更新哈希表
		            while(hash.size() > 2)
		            {
		                hash[fruits[left]]--;
		
		                // 如果当前水果种类已经为 0，删除哈希表中这种水果的种类
		                if(hash[fruits[left]] == 0)
		                    hash.erase(fruits[left]);
		
		                left++;
		            }
		
		            ans = max(ans, right - left + 1);
		        }
		
		        return ans;
		    }
		};

		class Solution {
		public:
		    vector<int> findAnagrams(string s, string p) 
		    {
		        vector<int> ret;
		        int hash1[26] = {0};
		        for(auto& ch : p) hash1[ch - 'a']++;
		        int len = p.size();
		
		        int hash2[26] = {0};
		
		        // count 维护s在p中的有效字符个数
		        int count = 0;
		        for(int left = 0,right = 0;right < s.size();right++)
		        {
		            hash2[s[right] - 'a']++;
		            if(hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) count++;
		
		            // 出窗口
		            if(right - left + 1 > len)
		            {
		                char out = s[left];
		                left++;
		
		                // 判断出窗口的字符是否是p中的有效字符，如果是则维护 count
		                if(hash2[out - 'a'] <= hash1[out - 'a']) count--;
		                hash2[out - 'a']--;
		            }
		            
		            if(count == len)
		            {
		                ret.push_back(left);
		            }
		        }
		        return ret;
		    }
		};

		class Solution {
		public:
		    vector<int> findSubstring(string s, vector<string>& words)
		    {
		        vector<int> ret;
		
		        // hash1 记录 words 中的字符串
		        unordered_map<string, int> hash1;
		        for (const auto& str : words) hash1[str]++;
		
		        // words 中每个字符串的长度
		        int strLen = words[0].size();
		
		        // 遍历前 strLen 个即可
		        for (int i = 0; i < strLen; i++)
		        {
		            // hash2 记录组合成的字符串
		            unordered_map<string, int> hash2;
		            for (int left = i, right = i, count = 0; right < s.size(); right += strLen)
		            {
		                string in = s.substr(right, strLen);
		                hash2[in]++;
		
		                // count 维护有效字符串的数量，符合则 ++ 
		                if (hash2[in] <= hash1[in])
		                    count++;
		
		                // 出窗口判断
		                if (right - left + 1 > strLen * words.size())
		                {
		                    string out = s.substr(left, strLen);
		                    if (hash2[out] <= hash1[out])
		                        count--;
		                    hash2[out]--;
		                    left += strLen;
		                }
		
		                if (count == words.size())
		                {
		                    ret.push_back(left);
		                }
		            }
		        }
		
		        return ret;
		    }
		};

		class Solution {
		public:
		    string minWindow(string s, string t) 
		    {
		        int hash1[128] = {0};
		
		        // kinds 统计 t 中字符类型的数量
		        int kinds = 0;
		        for(auto& ch : t) if(hash1[ch]++ == 0) kinds++;;
		
		        int hash2[128] = {0};
		        int minLen = INT_MAX, begin = -1;
		        for(int left = 0,right = 0,count = 0;right < s.size();right++)
		        {
		            hash2[s[right]]++;
		
		            // 字符出现的次数必须等于hash1中的次数，窗口维护的有效字符类型才可以统计
		            if(hash2[s[right]] == hash1[s[right]]) count++;
		
		            while(count == kinds)
		            {
		                if(right - left + 1 < minLen)
		                {
		                    minLen = right - left + 1;
		                    begin = left;
		                }
		                char out = s[left];
		                left++;
		
		                if(hash2[out] <= hash1[out]) count--;
		                hash2[out]--;
		            }
		
		            
		        }
		
		        if(begin == -1) return "";
		        return s.substr(begin, minLen);
		    }
		};