8 - 滑动窗口
准备春招，算法题冲冲冲！
滑动窗口
滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
练习题
定长滑动窗口
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
我们用哈希表来存储字符的出现状态：
// 初始化
unordered_map<char, int> hash;
for (auto ch : p)
hash[ch]++;
接下来就要用双指针了：
- 拓展R，让
hash[right]--表示right已进入滑动窗口。 - 缩小L，由于
hash[ch]只存在0和1，如果是负数，说明该字母不在子串中，这时候就要收缩L，让left退出滑动窗口，直到hash[right] >= 0。 - 如果滑动窗口的长度刚好是
p的长度，说明我们找到了字母异位词，可以存储答案left。
代码如下：
for (int left = 0, right = 0; right < s.size(); right++)
{
hash[s[right]]--;
while (hash[s[right]] < 0)
{
hash[s[left++]]++;
}
if (right - left + 1 == p.size())
ans.push_back(left);
}
不定长滑动窗口(求最长/最大)
3. 无重复字符的最长子串 - 力扣（LeetCode）
使用双指针模拟即可，这里需要注意，先检查是否要缩小滑动窗口，然后才扩展滑动窗口。
int lengthOfLongestSubstring(string s) {
unordered_set<char> hash;
int ans = 0;
for (int left = 0, right = 0; right < s.size(); ++right)
{
while (left <= right && hash.contains(s.at(right)))
hash.erase(s.at(left++));
hash.insert(s.at(right));
ans = max(ans, right - left + 1);
}
return ans;
}
不定长滑动窗口(求最短/最小)
209. 长度最小的子数组 - 力扣（LeetCode）
例子：target = 7，nums = 3。
- 队空，2入队，sum = 2 < 7
- 3入队, sum = 5 < 7
- 1入队, sum = 6 < 7
- 2入队, sum = 8 >= 7。看看队头能否出队，以减少队伍长度，不行。队长 114514 -> 4
- 4入队, sum = 12 >= 7。队头2出队，sum = 10 >= 7；队头3出队， sum = 7 >= 7。队长 4 -> 3
- 3入队, sum = 10 >= 7。队头1出队，sum = 9 >= 7；队头2出队，sum = 7 >= 7。队长 3 -> 2。
最终得到最短长度的子数组，3。
代码如下：
int minSubArrayLen(int target, vector<int>& nums) {
// 滑动窗口
int ans = 114514;
int sum = 0;
for (int left = 0, right = 0; right < nums.size(); ++right)
{
// 拓展R
sum += nums.at(right);
// 缩小L
while (left <= right && sum - nums.at(left) >= target)
{
sum -= nums.at(left++);
}
// 最后康康有没有答案
if (sum >= target)
{
ans = min(ans, right - left + 1);
}
}
return ans == 114514 ? 0 : ans;
}
不定长滑动窗口（求子数组个数）
713. 乘积小于 K 的子数组 - 力扣（LeetCode）
首先，如果k是小于等于1的，那就没有答案，因为数据范围是 1<= nums[i] <= 1000.
接下来开始做题，和 长度最小的子数组 这道题思路差不多，我们通过一直乘nums[right]来拓展滑动窗口，接下来如果乘积大于等于k，那么就通过一直除nums[left]来缩小滑动窗口。
最后得到位于[left, right]的滑动窗口内元素乘积一定小于k。那么[left + 1, right]内元素乘积也一定小于k，... ，[right, right]内元素乘积也一定小于k。因此符合条件的子数组有right - left + 1个。
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1)
return 0;
int ans = 0;
int mul = 1;
for (int left = 0, right = 0; right < nums.size(); ++right)
{
// 拓展r
mul *= nums.at(right);
// 缩小l
while (left <= right && mul >= k)
mul /= nums.at(left++);
// [l, r]的乘积一定小于k
// 那么 [l+1, r], ... , [r, r]乘积均小于k
ans += right - left + 1;
}
return ans;
}