滑动窗口法

什么情况下会想到滑动窗口法：

任何题目如果没有思路其实都可以想一下暴力解法。这道题暴力解法思路简单：

遍历任意i，j，使得i和j之间的子串长度，等于p串的长度。该子串称之为x。该步复杂度为O（n）。 判断x是否与p是异位词。是的话，则把i加入答案中。该步复杂度为O（n）。 暴力法的复杂度为O（n^2）。显然不高效。

可以发现第二步其实做了很多不必要的操作，例如[i, j]和[i+1, j+1]两个子串在暴力法第二步中，需要各遍历一次，完全没必要。其实[i+1, j+1]完全可以在[i, j]的基础上做判断，也就是去掉头部的字符（i位置），加上尾部的字符（j+1位置）。这样第一步的复杂度可以降到O(1)。整体复杂度降到O(n)。已经得到信息不重复使用就浪费了，没必要重新搜集近乎相同的信息。这就是滑动窗口法。

滑动窗口法的特点是，一连串元素的信息，可以用常数时间推断出，该串整体移位后，新串信息。

所有滑动窗口问题，如果能从暴力法优化的角度思考，都不难想到。

双指针

1
2
3
4
5
6
7
8
9

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

medium

和为S的连续正数序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int> > res;
        if(sum==0||sum==1) return res;
        vector<int> cur;
        int count = 0;
        for(int i =1,j=1;i<=sum/2+1;i++){
            count+=i;
            while(count>sum){
                count-=j++;
            }
            if(count==sum){
                for(int k =j;k<=i;k++){
                    cur.push_back(k);
                }
                res.push_back(cur);
                cur.clear();
            }
        }
        return res;
    }
};

字符流中第一个只出现一次的字符

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution{
public:

    //记录每个字符出现的个数
    map<char, int>buff;
    //y总说了：双指针和单调队列有点相似(狗头
    queue<int>q;
    void insert(char ch){
        //如果buff里面的记录的ch个数为1，并且队列不为空，对头头元素的个数大于1
        //队列里面可能会空，但是buff里面一直已经存在的字符
        if (++ buff[ch] > 1) {
            while (q.size() && buff[q.front()] > 1) q.pop();
        } else {
            q.push(ch);
        }
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        if (q.empty()) return '#';
        else return q.front();
    }
};

3. 无重复字符的最长子串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> hash;
        int res=0;
        for(int i=0,j=0;j<s.size();j++)
        {
            hash[s[j]]++;
            while(hash[s[j]]>1)
            {
                hash[s[i++]]--;
            }

            res=max(res,j-i+1);
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n =s.length();
        unordered_set<char> st;
        if(n==0) return 0;
        int maxStr = 0,left=0;
        for(int i =0;i<n;i++){
            while(st.find(s[i])!=st.end()){
                st.erase(s[left]);
                left++;
            }
            st.insert(s[i]);
            maxStr = max(maxStr,i-left+1);
        }
        return maxStr;
    }
};

643. 子数组最大平均数 I

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double res=-5e4-5.5;
        int n = nums.size(),left=0,len=0;
        double sum = 0.0;
        for(int i =0;i<n;i++){
            sum+=nums[i];
            len++;
            while(len==k){
                res=max(res,sum/k);
                sum-=nums[left];
                left++;
                len--;
            }           
        }
        return res;
    }
};

209. 长度最小的子数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int left=0,res=n,sum=0;
        bool flag =false;
        for(int i = 0;i<n;i++){
            sum+=nums[i];
            while(sum>=target){
                res=min(res,i-left+1);               
                sum-=nums[left];
                left++;
                flag=true;
            }
        }
        if(flag) return res;
        else return 0;
    }
};

1695. 删除子数组的最大得分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> st;
        int left =0;
        int res =0,sum=0;
        for(int i =0;i<n;i++){
            while(st.find(nums[i])!=st.end()){
                st.erase(nums[left]);
                sum-=nums[left];
                left++;               
            }
            st.insert(nums[i]);
            sum+=nums[i];
            res=max(res,sum);
        }
        return res;
    }
};

438. 找到字符串中所有字母异位词

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        int n = s.length(),m=p.length();
        if(n<m) return result;
        vector<int> a(26,0);
        vector<int> b(26,0);
        for(int i =0;i<m;i++) b[p[i]-'a']++;
        int left = 0;
        for(int i =0;i<n;i++){
            a[s[i]-'a']++;            
            if(i>=m){
                a[s[left]-'a']--;
                left++;
            }
            if(a==b) result.push_back(left);
        } 
        return result;
    }
};

567. 字符串的排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(),m=s2.length();
        if(n>m) return false;
        vector<int> a(26,0);
        vector<int> b(26,0);
        for(int i = 0;i<n;i++){
            a[s1[i]-'a']++;
        }  
        int left=0;
        for(int i =0;i<m;i++){
            b[s2[i]-'a']++;
            if(i>=n){
                b[s2[left]-'a']--;
                left++;
            }
            if(a==b) return true;
        }
        return false;
    }
};

1004. 最大连续1的个数 III

 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

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> a; 
        int res = 0;
        for(int i =0;i<n;i++){                      
            while(k==0&&nums[i]==0){
                if(a.front()==1){
                    a.pop_front();                    
                }else{
                    a.pop_front();
                    k++;
                }
            }
            if(nums[i]==0){
                k--;               
            }
            a.push_back(nums[i]);
            int t = a.size();
            res=max(res,t); 
            
        }
        return res;
    }
};

1208. 尽可能使字符串相等

 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

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int res = 0;
        int n = s.length();
        int a[n];
        vector<int> b(n,0);        
        for(int i =0;i<n;i++){
            a[i]=abs(s[i]-t[i]);
        }
        int left=0,len=0;
        for(int i = 0;i<n;i++){
            b[i]=a[i];
            maxCost-=a[i];
            len++;
            while(maxCost<0){
                maxCost+=b[left];
                left++;
                len--;                    
            }
            res=max(res,len);
        }
        return res;
    }
};

1052. 爱生气的书店老板

 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

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int n = customers.size();
        int sum = 0;
        int res=0;
        vector<int> v;
        for(int i =0;i<n;i++){
            if(grumpy[i]==0) sum+=customers[i];
            else{
                v.push_back(i);
            }
        }
        int left = 0;
        for(int i =0;i<v.size();i++){            
            while(v[i]-v[left]>=minutes){
                sum-=customers[v[left]];
                left++;
            }
            sum+=customers[v[i]];
            res=max(res,sum);
        }
        res=max(res,sum);
        return res;
    }
};

1423. 可获得的最大点数

 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

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        int res = 0,sum=0,left=n-k,len=k;
        vector<int> d;
        for(int i = 0;i<n;i++){
            d.push_back(cardPoints[i]);
        }
        for(int i = 0;i<n;i++){
            d.push_back(cardPoints[i]);
        }
        for(int i =n-k;i<n+k;i++){
            sum+=d[i];
            len--;
            res=max(res,sum);
            if(len==0){
                sum-=d[left];
                left++;
                len++;
            }           
        }
        return res;
    }
};

hard

30. 串联所有单词的子串

思路 总共用到两个哈希表，allWordsMap用于记录words中单词出现的次数，nowWordsMap用于记录子串中（也就是滑动窗口中）单词出现的次数 num为单词的个数，onelen为单词长度 遍历字符串，移动长度为 num* onelen的滑动窗口，再在当前滑动窗口中依次比较onelen长度的单词 当这个窗口内一旦出现不存在allWordsMap中的单词，或者这个单词在子串中出现的次数已经等于allWordsMap中的次数(也就是再加入这个子串次数就要超出了)，这个滑动窗口就不符合要求，直接break进入下一个滑动窗口的匹配 一旦完全匹配上了，把滑动窗口的起始索引加入结果res中

 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
37
38

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> allWordsMap;
        for (auto& v : words) {
            allWordsMap[v]++;
        }
        
        int num = words.size();
        int onelen = words[0].length();
        vector<int> res;
        if (s.length() < num * onelen) {
            return res;
        }
        
        for (int left = 0; left < s.length() - num * onelen + 1; ++left)
        {
            unordered_map<string, int> nowWordsMap;
            int right = left;
            while (right < left + num * onelen) {
                auto cur = s.substr(right, onelen);
                if (allWordsMap.find(cur) == allWordsMap.end() 
                    || nowWordsMap[cur] == allWordsMap[cur]) {
                    break;
                }
                
                ++nowWordsMap[cur];
                right += onelen;
            }
            
            if (right == left + num * onelen) {
                res.push_back(left);
            }
        }
        
        return res;
    }
};

76. 最小覆盖子串

239. 滑动窗口最大值