算法：滑动窗口

例题1：长度最小的子数组

长度最小的子数组

分析：
若暴力枚举，用三重循环列出所有可能：

int n = nums.size();
for(int i = 0; i < n; i++){//以i位置开头的所有子数组
	for(int j = i; j < n; j++){//以j位置为结尾
		int n = 0;
		for(int k = i; k <= j; k++){//依次算出各个子数组的和，然后比较和大于等于target的子数组的长度那个最小
			n += nums[k];
………………………………………………………………
//时间复杂度 O(N^3)
1
2
3
4
5
6
7
8

简单的优化：计算子数组和时不需要每次都从头开始

int n = nums.size();
for(int i = 0; i < n; i++){//以i位置开头的所有子数组
	int n = 0;
	for(int j = i; j < n; j++){
		n += nums[j];
	
//时间复杂度 O(N^2)
1
2
3
4
5
6
7

因为这道题说数组中的数全为正整数，所以 += 操作后 n 肯定是递增的（单调性） —— 当 n >= target 时就没有继续 += 的必要了，此时 n 就是这个循环中 长度最小的、和大于等于target的子数组的和

以 2 3 1 2 4 3（target = 7） 为例，第一层循环过后，我们知道了以0位置开头的子数组中，2 3 1 2 是我们想要的；第二次循环会从3开始，我们需要再从头开始枚举子数组吗 —— 我们可以记录第一次循环结束位置，然后直接以3 1 2为基础继续

● 根据以上的分析，我们改用两个指针（同向双指针（同向指两个指针都不回退，向着一个方向移动））来实现上述的操作：

left 和 right 两个“指针”之间形成一个区间，并记录（维护）着这个区间内的信息（子数组和、长度），两个指针从左向右移动的过程中，这个区间就像一个窗口一样在数组中滑动 —— 滑动窗口

以上的思路为：利用单调性，使用“同向双指针（滑动窗口）”优化问题

● 怎么用：
1.left = 0，right = 0
2.进窗口
3.判断 <-> 出窗口

● 这个方法的正确性：
利用单调性，规避了很多没有必要的枚举行为

在暴力解法中若发现了单调性，可以考虑用这个方法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), sum = 0, len = INT_MAX;//结果
        for(itn left = 0, right = 0; right < n; right++){
            sum += nums[right];//进窗口（新进入left和right之间的数据，会产生什么影响--sum+=nums[right]）
            while(sum >= target)//判断
            {
                len = min(len, right - left + 1);//更新结果 -- 可能在判断后，也可能在出窗口后（因题而异）
                sum -= num[left++];//出窗口（left++过后，左侧数据不再处于left和right之间）
            }
        }
        return len;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

● 时间复杂度：
我们的每一步操作都让 left / right 向右移动，直至最后 -> O(N)

例题2：无重复字符的最长子串

无重复字符的最长子串

暴力解法：暴力枚举（从左往右依次枚举以左侧数字为开头的满足要求的所有子串）-- 判断满足要求：可以用哈希表储存已遍历子串部分的字符，依次判断字符是否重复

模拟：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0};//使用数组模拟哈希表，0表示没有，1出现一次，2出现两次
        int len = 0;
        for(int left = 0, right = 0; right < s.size(); right++){
            hash[s[right]]++;//进窗口
            while(hash[s[right]] > 1)//判断 
                hash[s[left++]]--;//出窗口
            len = max(len, right - left + 1);//更新结果
        }
        return len;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

例题3：最大连续1的个数 III

最大连续1的个数 III

问题转化：找出0的个数不超过k个的最长子数组

暴力求解：从左往右依次以每个数为开头，往后找最长可以到哪 ->O(N^2)
模拟示例1：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        for(int left = 0, right = 0, zero = 0; right < nums.size(); right++){//zero记录0的个数
            //对于right而言，1进窗口时不用管
            if(nums[right] == 0) zero++;//0进窗口
            while(zero > k)//判断
                if(nums[left++] == 0) zero--;//出窗口
            ret = max(ret, right - left + 1);//更新结果
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

例题4：将 x 减到 0 的最小操作数

将 x 减到 0 的最小操作数

分析：

正 难 则 反

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        //题目说了nums[i]>0
        int sum_ = 0;
        for(auto e : nums) sum_+= e;
        int target = sum_ - x;
        if(target < 0) return -1;//!
        int n = nums.size(), len = -1;
        for(int left = 0, right = 0, sum = 0; right < n; right++){
            sum += nums[right];//入窗口
            while(sum > target){//判断
                sum -= nums[left++];//出窗口       
            }
            if(sum == target) 
                len = max(len,right - left + 1);//更新结果
        }
        return len == -1 ? -1 : n - len;//如果len初始被赋予 0，这地方用len == 0做判断，遇到 target == 0 的情况会出问题
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

例题5：水果成篮

水果成篮

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int hash[100001] = {0};//数组模拟哈希表，表示各水果类型所持数目 
        //也可以用unordered_map，似乎更方便些
        
        //题目说 1 <= fruits.length <= 10^5，结果开10010个空间不给过，合着 <= 10^5的意思是数量级不是具体数呗，这个老六
        int num = 0, sort = 0;
        for(int left = 0, right = 0; right < n; right++){
            if(hash[fruits[right]] == 0) sort++;
            hash[fruits[right]]++;//入窗口
            while(sort > 2){
                if((--hash[fruits[left++]]) == 0)//出窗口
                    sort--;
            }
            num = max(num, right - left + 1);
        }
        return num;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个方法我和老师写的几乎一模一样 —— 我终于出息了（

老师用哈希表的演示：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> hash;
        int ret = 0;
        for(int left = 0, right = 0; right < fruits.size(); right++){
            hash[fruits[right]]++;//进窗口
            while(hash.size() > 2){
                //出窗口
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0)
                    hash.erase(fruits[left]);
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

例题6：找到字符串中所有字母异位词

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

不同于之前的题目的是，这道题的滑动窗口是固定长度的（长度为p的大小）

可以用两个哈希表分别表示 p 中每个字符出现的次数 和 滑动窗口中每个字符出现的次数。通过比较两哈希表是否相同判断异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = {0};//p中每个字符出现的次数
        for(auto ch : p) hash1[ch-'a']++;
        int hash2[26] = {0};//滑动窗口中每个字符出现的次数
        vector<int> ret;
        for(int left = 0, right = 0, count = 0; right < s.size(); right++){
            char in = s[right];//进窗口的字符 
            hash2[in - 'a']++;//进窗口
            if(hash2[in - 'a'] <= hash1[in - 'a']) 
                count++;
            //判断
            if(right - left >= p.size()){//固定的窗口长度:p.size()
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;//出窗口
            }
            if(count == p.size()) ret.push_back(left);//更新结果
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

例题7：串联所有单词的子串

串联所有单词的子串

例题6 的加强版，试着将子串当做一整个数据（就像单个字符一样）

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash1;//存储 words 中的子串
        for(auto& str : words) hash1[str]++;
        int len = words[0].size();//一个子串的长度，可视作一个整体数据
        vector<int> ret;
        for(int i = 0; i < len; i++){//自不同的起点出发遍历所有情况
            unordered_map<string, int> hash2;//维护滑动数组内的子串
            for(int left = i, right = i, count = 0; right + len <= s.size(); right += len){
                string in = s.substr(right, len);//进窗口的子串
                hash2[in]++;//进窗口
                if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
                if(right - left >= len * words.size()){
                    string out = s.substr(left, len);//出窗口的数据
                    if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    left += len;//出窗口
                }
                if(count == words.size()) ret.push_back(left);
            }
        }
        return ret;
    }
};
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

例题8：最小覆盖子串

最小覆盖子串

分析：

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[58] = { 0 };//开了57个空间，然后不够……建议直接开128个空间，还省去了后面 -'A' 的麻烦
        for (auto ch : t) hash1[ch - 'A']++;
        int hash2[58] = { 0 };
        int begin = -1, len = INT_MAX;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];//进窗口数据
            hash2[in - 'A']++;//进窗口
            if (hash2[in - 'A'] <= hash1[in - 'A']) count++;
            while (count == t.size()) {//判断
                if (right - left + 1 < len) {//更新结果
                    len = right - left + 1;
                    begin = left;
                }
                char out = s[left];//出窗口数据
                if (hash2[out - 'A'] <= hash1[out - 'A']) count--;
                hash2[out - 'A']--;//出窗口
                left++;
            }
        }
        return len == INT_MAX ? "" : s.substr(begin, len);
    }
};
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