【c++算法篇】滑动窗口

🔥个人主页：Quitecoder

🔥专栏：算法笔记仓

操作滑动窗口通常涉及以下几个步骤：

1. 初始化两个指针，通常称为 left 和 right，指向序列的起始部分，这定义了窗口的边界。

2. 根据问题的需要，将 right 指针向右移动以扩大窗口，直到窗口中的元素满足特定条件（例如，元素总和达到目标值）。

3. 当窗口中的元素满足特定条件之后，可能需要将 left 指针向右移动以缩小窗口，并再次检查条件是否满足。在移动 left 指针的同时，我们可以更新相关的计算结果，如累积和或计数器等

4. 在整个过程中，我们通常会记录窗口相关的一些信息，如窗口大小、窗口内元素的总和、窗口中的最大或最小元素等，可能还会记录与问题计算要求相关的最优结果

5. 持续这个过程，有序地移动 left 和 right 指针，直到滑动窗口穷尽了整个序列的所有可能的连续元素集

一个常见的滑动窗口问题示例是找出一个数组中和至少为 target 的最短连续子数组，在这样的问题中，滑动窗口技术能够有效地找到解决方法，同时保证时间复杂度最少。

1.长度最小的子数组

题目链接：209. 长度最小的子数组
题目描述：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int right =0,left=0,len=INT_MAX;
        int sum=0;
        while(right<nums.size())
        {
            sum+=nums[right];
            while(sum>=target)
            {
                len=min(len,right-left+1);
                sum-=nums[left++];
            }
           right++;
        }
        return len==INT_MAX?0:len;
    }
};

这段代码解决的问题是寻找数组 nums 中和至少为 target 的最短连续子数组的长度。使用了滑动窗口方法，以下是它的逻辑和思路：

1. 初始化两个指针 left 和 right, 以及 sum 来存储当前窗口中的元素和，和 len 来存储最短子数组的长度。这里，len 初始化为 INT_MAX，表示一个非常大的数，用来保证能找到比初始值小的最小长度

2. 使用外层 while 循环遍历数组，右指针 right 逐渐向右移动，遍历数组的每个元素。

3. 在每次迭代中，把 right 指向的当前元素加到 sum 中。这扩大了当前的滑动窗口，包括了 right 指向的新元素

4. 出现滑动窗口中的和大于等于 target 时，进入内层 while 循环。在内层循环中：

   a. 通过 min(len, right-left+1) 更新 len 的值，以保持记录最短连续子数组的长度。

   b. 尝试缩小窗口从而找到可能的更短的连续子数组，方法是减去滑动窗口左端的元素值 nums[left]，然后将左指针向右移动一位 (left++)

5. 继续执行外层 while 循环，右指针向右移动 (right++)。每次增加 right 时，重复上述过程，更新窗口中的元素和 sum，然后再次检查窗口的和是否大于等于 target

6. 当外层 while 循环结束时（即遍历了所有元素），检查最短长度 len 是否被更新过：如果 len 还是 INT_MAX，这意味着没有找到满足条件的子数组，函数返回 0；否则，返回找到的最短连续子数组的长度

这个时间复杂度是 O(n)，因为每个元素最多被访问两次：一次是右指针向右移动时，另一次是左指针向右移动时

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

题目链接：3. 无重复字符的最长子串
题目描述：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128]={0};
        int left=0,right=0,len=0;
        while(right<s.size())
        {
            hash[s[right]]++;
            while(hash[s[right]]>1) hash[s[left++]]--;
            len=max(len,right-left+1);
            right++;
        }
        return  len;
    }
};

寻找给定字符串 s 中最长不含重复字符的子串的长度。使用滑动窗口，并在窗口内部跟踪了字符的出现情况。具体思路：

1. hash 数组用来维护每个 ASCII 字符在当前考虑的子串（滑动窗口）中的出现次数。它被初始化为0。

2. left 和 right 两个指针用来表示滑动窗口的边界，初始时都指向字符串的开头

3. len 用来保持找到的最长不重复字符子串的长度

4. 外层 while 循环用于移动 right 指针，这扩大了当前考虑的窗口

5. 每次迭代中，在 hash 数组中增加 right 指向字符的计数

6. 内层 while 循环检查通过 right 新加入的字符是否导致了重复字符出现。如果是这样，循环就使用 left 指针向前移动直到这个字符的计数再一次变为1

7. 窗口内的字符统计更新后，计算当前窗口的长度并与之前的 len 比较，取较大者作为新的 len

8. right 指针向前移动一位，以便包含当前右边界的下一个字符。

9. 外层循环直到 right 到达字符串的末尾结束，这时所有可能的窗口都已经被考虑。

10. 最终 len 就是最长不重复字符子串的长度。

代码结束时返回的 len 是所求的最长子串长度

3.最大连续1的个数 III

题目链接：1004. 最大连续1的个数 III
题目描述：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left=0,right=0,len=0,zero=0;
        while(right<nums.size())
        {
            if(nums[right]==0)zero++;
            while(k<zero)
            {
                if(nums[left]==0) zero--,left++;
                else left++;
            }
            len=max(len,right-left+1);
            right++;
        }
        return len;  
    }
};

同样的思路，用zero来记录零的个数，如果zero大于二，移动左指针指导等于二位置，继续将right向右移动，最后返回len的最大值

4.将 x 减到 0 的最小操作数

题目链接：1658.将 x 减到 0 的最小操作数
题目描述：

正难则反：

本题可以转换为，求中间最长连续数组的和为数组总和减去x的结果

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {

    int sum=0;
    for(int e:nums)
    {
        sum+=e;
    }
    int des=sum-x;
    if(des<0)
    return -1;
    int left=0,right=0,len=-1,add=0;
    while(right<nums.size())
    {
        add+=nums[right];
        
        while(add>des)
        {
            add-=nums[left++];
        }
        if(add==des)
        {
            len=max(len,right-left+1);
        }
        right++;
    }
    return len==-1?-1:nums.size()-len;
    
    }
};

des是中间连续数组的目标求和值，add记录连续子数组的和，如果和大于目标值，则让add减去左指针指向的值并让左指针移动，如果等于则记录最大值，这里初始值给-1，如果没有匹配的数组，则返回-1

5.水果成篮

题目链接：904.水果成篮
题目描述：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001]={0};
        int left=0,right=0,len=0,kinds=0;
        while(right<fruits.size())
        {
            if(hash[fruits[right]]==0) kinds++;
            hash[fruits[right]]++;
            while(kinds>2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]]==0)
                kinds--;
                left++;
            }
            len=max(len,right-left+1);
            right++;
        }
        return len;
    }
};

在给定一个整数数组 fruits 的情况下，找到最长的连续子数组（窗口），其中只包含最多两种不同的元素（即果树种类）。这个问题可以用滑动窗口算法解决：

1. hash 数组用来计数每种水果当前在窗口中的数量。

2. 两个变量 left 和 right 表示当前窗口（子数组）的两端位置。

3. len 用来记录窗口的最大长度。

4. kinds 用来记录当前窗口中有多少种不同的水果

代码的逐步逻辑：

1. 外部 while 循环通过移动 right 指针向右扩展窗口，这样就能包含新的元素（水果种类）。

2. 如果当前 right 指针指向的水果种类之前未包含在窗口中（即 hash[fruits[right]] == 0），则增加 kinds 变量。

3. 然后增加该水果种类的计数（hash[fruits[right]]++）。

4. 内部 while 循环检查 kinds 是否超过了2。如果是这样，这表示当前窗口包含了超过两种水果，不符合题目条件。在这种情况下，需要缩小窗口（移动 left 指针）直到窗口中只包含两种水果。

5. if(hash[fruits[left]] == 0)这句代码检查减去左指针后是否已经不包含这种水果，如果不包含，则种类数 kinds 需要减少

6. 此次循环结束后，更新窗口长度的最大值 len（max(len, right - left + 1)）。

7. 当所有元素都被扩展到窗口中后，right 指针继续向右移动，让外部循环继续执行。

8. 当循环结束时，len 中存储的就是满足条件的最大窗口长度。

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

题目链接：438.找到字符串中所有字母异位词
题目描述：

• 因为字符串 p 的异位词的长度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构
  造⼀个长度为与字符串 p 的长度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；
• 当窗口中每种字母的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗口为字符串 p
  的异位词；
• 因此可以用两个大小为 26 的数组来模拟哈希表，⼀个来保存 s 中的子串每个字符出现的个
  数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;  
        if (s.length() < p.length()) {
            return result;
        }
        
        int left = 0, right = 0, n = p.size(), count = 0;
        int hash1[26] = {0};
        int hash2[26] = {0};

        for (char e : p) {
            hash1[e - 'a']++;
        }

        while (right < s.length()) {
            hash2[s[right] - 'a']++;
            if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) {
                count++;
            }
            
            if (right - left + 1 > n) {
                if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a']) {
                    count--;
                }
                hash2[s[left] - 'a']--;
                left++;
            }

            if (count == n) {
                result.push_back(left);
            }
            right++;
        }
        return result;
    }
};

：

1. 首先检查 s 的长度是否小于 p 的长度，如果小于，则直接返回空结果集，因为 p 的异位词长度必定与 p 相等

2. 定义并初始化两个长度为 26 的数组 hash1 和 hash2，这两个哈希表用于存储字符 ‘a’ 到 ‘z’ 在字符串 p 和当前检查的 s 的子串中出现的次数

3. 遍历字符串 p 并更新 hash1 表，其中 hash1[e - 'a']++ 表示将字符 e 在 hash1 中的计数增加 1，用于记录 p 里每个字符的频率

4. 使用两个指针 left 和 right 定义滑动窗口的边界。left 是窗口的起始位置，right 是窗口的结束位置，初始化时它们都是 0。变量 n 存储字符串 p 的长度，count 用于记录当前滑动窗口内字符频率匹配 p 中的字符频率的数量（即异位词的字符计数）

5. 开始遍历字符串 s，同时动态更新 hash2 表，并增加 count 计数，表达式 hash2[s[right] - 'a']++ 用于更新 s 中当前字符的频率

6. 如果当前字符在 hash2 里的计数小于或等于 hash1 中的对应计数，count 增加 1，这意味着这个字符是 p 中的字符，并且在目前窗口中的出现频率尚未超过 p 中的频率

7. 当滑动窗口的长度超过字符串 p 的长度时，必须移动窗口的左边界。如果要移出窗口的字符的频率在 hash2 中小于或等于 hash1，则减少 count 计数，并将 hash2[s[left] - 'a'] 减少 1，表示该字符从窗口中移除。

8. 如果 count 与 p 的长度相等，这意味着当前窗口是 p 的一个异位词，将当前窗口的起始索引 left 添加到结果集中。

9. 移动窗口的右边界以检查下一个字符。

10. 当遍历完成时，返回包含所有异位词起始索引的 result

与前面不同的是，这道题的窗口大小可以看做是固定的，left每次向右移动保证了窗口大小

7.串联所有单词的子串

题目链接：30.串联所有单词的子串
题目描述：

代码思路：与上一道题类似，我们把每个words里面的元素当成一个整体，然后对s进行整体的划分即可

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        if(s.empty() || words.empty() || words[0].size() > s.size())
            return ret;
        
        unordered_map<string, int> hash1; // 保存 words 里面所有单词的频次
        for(auto& word : words) hash1[word]++;
        int len = words[0].size(), m = words.size();
        
        int i = 0;
        while(i < len) { // 执行 len 次
            unordered_map<string, int> hash2; // 维护窗口内单词的频次
            int left = i, right = i, count = 0;
            while(right + len <= s.size()) {
                // 进窗口 + 维护 count
                string in = s.substr(right, len);
                if(hash1.count(in)) {
                    hash2[in]++;
                    if(hash2[in] <= hash1[in]) count++;
                }

                // 判断
                if(right - left + 1 > len * m) {
                    // 出窗口 + 维护 count
                    string out = s.substr(left, len);
                    if(hash1.count(out) && hash2[out] > 0) {
                        if(hash2[out] <= hash1[out]) count--;
                        hash2[out]--;
                    }
                    left += len;
                }

                // 更新结果
                if(count == m) ret.push_back(left);

                right += len; // 窗口右端向右移动
            }
            i++; // 处理下一个子串开始位置
        }

        return ret;
    }
};

继续构建两个哈希表

“执行 len 次”是指，对滑动窗口处理的起始点进行遍历，而遍历的次数等于单词的长度 len。每个单词长度相同，这个长度用 len 变量表示

8.最小覆盖子串

题目链接：76.最小覆盖子串
题目描述：

class Solution {
public:
    string minWindow(string s, string t) {
       string s1;
       if(s.size()<t.size())return s1;
       int hash1[128]={0};
       int hash2[128]={0};
       int kinds=0;
       int count=0;
       int len=INT_MAX;
       for(auto e:t)
       {
        if(hash1[e]++ == 0) kinds++;
       }
       int left=0,right=0;
       int start=0;
       while(right<s.size())
       {
         hash2[s[right]]++;
         if(hash2[s[right]]==hash1[s[right]])count++;
         while(count==kinds)
         {
            if(right - left + 1 < len) { 
                    len = right - left + 1;
                    start = left; 
            }
            hash2[s[left]]--;
            if(hash2[s[left]]<hash1[s[left]])count--;
            left++;
         }
         right++;
       }
       return len==INT_MAX?"":s.substr(start,len);
   }
};

思路：

1. 预处理：

   • 首先，检查 s 的长度是否小于 t 的长度。若是，则无法包含所有 t 中的字符，直接返回空字符串。
   • 初始化两个哈希数组 hash1 和 hash2 来分别记录 t 中每个字符的频率和当前窗口中每个字符的频率。数组大小设置为 128，以便覆盖所有 ASCII 字符。

2. 记录 t 中字符的频率：

   • 遍历字符串 t，并使用 hash1 统计每个字符出现的频率。
   • 如果字符 e 在 hash1 中的频率从 0 变为 1，意味着 t 中又有一个新的字符，因此将 kinds 计数加 1，kinds 表示 t 中不同字符的种类数。

3. 初始化变量：

   • 初始化计数器 count 为 0，用于记录当前窗口已满足的 t 中不同字符的数量。
   • 初始化 len 为 INT_MAX，用于记录目前找到的最小窗口的长度。
   • 初始化指针 left 和 right 为 0，它们表示滑动窗口的左右边界。

4. 移动右指针 right：

   • 使用 while 循环，移动右指针 right 来拓展当前窗口，直到涵盖了 t 中的所有字符。
   • 增加 hash2[s[right]] 的值，表示当前字符在窗口中的计数增加。
   • 如果 s[right] 在 hash2 中的计数与 hash1 中的计数相等，意味着至少包含了 t 中对应字符所要求的数量，count 加 1。

5. 检查并收缩窗口：

   • 当 count 与 kinds 相等时，意味着当前窗口覆盖了 t 中所有的字符。
   • 进入另一个 while 循环，尽可能缩小窗口大小，移动左指针 left，同时更新 len 和 start 来记录最小覆盖子串的位置和长度。
   • 在移动 left 指针之后，将 hash2[s[left]] 相应的值减少。如果减少后 hash2[s[left]] 的值小于了 hash1[s[left]]，意味着不能再移动 left 指针，因为移除的字符是 t 中必须有的字符，所以窗口不再满足条件，需停止收缩。

6. 移动右指针直到末尾：

   • 继续移动右指针 right，寻找下一个满足条件的窗口。

7. 返回结果：

   • 当右指针遍历完 s 后，检查记录的 len 是否变化，如果为 INT_MAX，表示没有找到合适的窗口，返回空字符串。
   • 如果 len 不为 INT_MAX，意味着找到了最小窗口子串，通过 s.substr(start, len) 获取该子串并返回。