环己三烯的冬眠舱

天天网抑云，偶尔读点书。

0%

滑动窗口

发表于 更新于

概述

没什么好说的，直接看题吧。

例题 1

先来道简单的热热身。

LeetCode 713. 乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

1
2
3
4
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2:

1
2
输入：nums = [1,2,3], k = 0
输出：0

题解 1

一开始还以为子数组的定义是中间可以间断的，比如示例 1中 [10,2] 也可以算一个答案，于是第一反应是二进制枚举法，一看数据范围最大有 10⁴ 个元素，于是就放弃了。后面看了半天题解才反应过来，原来必须是连续的元素才能叫子数组，太坑了！

既然必须是连续的元素，那就可以用滑动窗口来枚举。每轮循环窗口右边界向右移动，再一边判断一边把左边界向右移动，得到乘积小于目标值的最大子数组，再进一步计算就可以得到当前右边界下满足条件的子数组数量。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int l=0;int r=0;
        if(k==0) return 0;
        int n=nums.size();
        int sum=1;
        int res=0;
        for(r;r<n;r++){ //每轮循环将右边界往右滑动一个单位
            sum*=nums[r];
            while(l<=r && sum>=k){ //依据当前右边界滑动左边界
                sum/=nums[l];
                l++;
            }
            res+=r-l+1; //比当前子数组小的都满足条件
        }
        return res;
    }
};

例题 2

再来一道“稍微”难一点的，其实写起来也差不太多，只是题目绕了点。

LeetCode 30. 串联所有单词的子串

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

1
2
3
4
5
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

1
2
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

示例 3：

1
2
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

题解 2

由于题目说 words 里的单词长度都是相同的（记为len ），那么我们就可以每次滑动 len 的距离。考虑到 s 中的单词不一定是整倍整倍出现的，比如 s="aababab" ，words=["ab","ab","ab"] 如果只从 0 开始构建移动窗口的话会刚好错过全部的 ab 。所以我们应该把 [0,len] 中的全部数都做一遍开头。

另外一个小tips就是因为题目里是不考虑 words 中元素出现的顺序的，所以可以直接使用哈希表计数，方便统计。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int len=words[0].size();
        int n=s.length();
        int limit=words.size()*len; //窗口长度。此处为定长，上面那题是变长。
        vector<int> res;
        unordered_map<string,int> need;
        for(string i : words) need[i]++;
        for(int i=0;i<len;i++){ //[0,len）每个都当一次开头，避免有单词被拦腰截断。
            int l=i; int r=i;
            int cnt=0;
            unordered_map<string,int> window;
            while(r<n){
                string rightstr=s.substr(r,len);
                if(need.count(rightstr)>0){
                    window[rightstr]++;
                    if(window[rightstr]==need[rightstr]) cnt++;
                }
                r+=len;
                if(r-l>limit){
                    string leftstr=s.substr(l,len);
                    if(need.count(leftstr)>0){
                        if(window[leftstr]==need[leftstr]) cnt--;
                        window[leftstr]--; //先判断是否相等再减。
                    }
                    l+=len;
                }
                if(r-l==limit && cnt==need.size()){
                    res.push_back(l);
                }
            }
        }
        return res;
    }
};

有的没的

折磨永存

从那天开始我就陷入了没有尽头的等待。我还清晰地记得中考那天，因为我已经可以去缙中了可以随便考考，于是慷慨地把手表借给了同学。考场没有闹钟（其实有，但是在教室后面，怕被打成作弊不敢回头看），忘了考的什么科目了，反正我早早地写完了题目，也不知道还剩多久时间，就在教室里干等，那简直是我记忆中最漫长的等待。现在的情况比那个时候更糟，因为那个时候我还知道等待一定是有尽头的，考试是会结束的，而现在我不知道要等多久，不知道等待有没有尽头，想放弃又怕万一再坚持一下下就可以了，而又没有足够的动力和勇气支撑我继续坚持。现在的我只是逃避接受现实所以一直在拖延罢了。情感生活上我从来就不是一个洒脱的人，在认识到这一点之后就愈发不敢轻易地对一个人动心了。

我的情感生活真是过得稀烂。 ——节选自1019事变

网抑云（孙燕姿 - 我怀念的）