准备春招，算法题冲冲冲！

滑动窗口

个人感觉和双指针算法差不多，但是这里要先扩充窗口，再缩小窗口，强调对双指针的一个规律维护。

练习题

定长滑动窗口

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

我们用哈希表来存储字符的出现状态：

// 初始化
unordered_map<char, int> hash;
for (auto ch : p)
    hash[ch]++;

接下来就要用双指针了：

1. 拓展R，让hash[right]--表示right已进入滑动窗口。
2. 缩小L，由于hash[ch]只存在0和1，如果是负数，说明该字母不在子串中，这时候就要收缩L，让left退出滑动窗口，直到hash[right] >= 0。
3. 如果滑动窗口的长度刚好是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 = {2, 3, 1, 2, 4, 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。

最终得到最短长度的子数组，{4, 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;
}

多指针滑动窗口

参考资料

• 分享丨【题单】滑动窗口（定长/不定长/多指针） - 力扣（LeetCode）
• 算法基础课 - AcWing