【优选算法】滑动窗口

滑动窗口基础知识和操作

首先这里对滑动窗口做一些了解

一、滑动窗口的本质是什么？
答：同向双指针

二、滑动窗口在什么情况下使用？
答：当我们暴力求解时，两个指针向同一个方向移动，并且两个指针没有回退的情况。

三、滑动窗口如何使用？
答：

1. 定义两个变量 left 和 right都赋值为0
2. 元素进窗口
3. 判断，符合条件则元素出窗口
4. 更新结果（这里并不是真正的第四步，更新结果这个步骤需要看确切的题目，有可能在进窗口更新，也有可能在出窗口更新）

这里需要重复2 、 3两个步骤，直到不符合循环条件

四、滑动窗口是如何保证正确性的？
答：利用单调性，规避了很多暴力求解中没有必要的枚举。

五、滑动窗口的时间复杂度是多少？
答：滑动窗口的时间复杂度是$O(N)$

---

一、长度最小的子数组

题目描述：

思路讲解：
首先我们看到会想到暴力解法，就是将所有的子数组全部列举出来后相加，取其中最小的返回。
然后我们可以通过暴力解法的步骤可以发现与双指针非常相似，定义两个变量left = 0 ， right = 0，定义一个变量len记录最小子数组的长度，再定义一个变量sum来记录子数组的和，right 向后遍历

1. 当 sum < target 时，right 继续向后遍历
2. 当 sum > target 时，说明从left开始到right或后面的连续子数组的和必定大于 target ， 所以 right 后面的数字就可以不继续遍历，然后将left向后+1，将更新后left赋值给right，重置sum的值，再重复上面的内容。
3. 当 sum == target 时，使当前区间的长度与len进行比较，取小的值赋值给len，然后将left向后+1，将更新后left赋值给right，重置sum的值，再重复上面的内容。

当left遍历到数组的末尾时结束循环，返回len完成本题。

然后我们通过暴力求解的方式可以发现right每次都向前重置是没有必要的，换一种思路：

1. 当 sum < target 时，right 继续向后遍历
2. 当 sum > target 时，说明从left开始到right或后面的连续子数组的和必定大于 target ， 所以 right 后面的数字就可以不继续遍历，然后将left持续向后移动直到sum 与 target 的关系变为其他两种情况，那么进行其他两种情况的操作。
3. 当 sum == target 时，使当前区间的长度与len进行比较，取小的值赋值给len，然后将left向后+1，那么 sum 的值必定会小于 target，那么继续进行 sum < target 关系的操作。

当right遍历到数组的末尾时结束循环，返回len完成本题。

通过上面思路的转换我们可以发现，在没有很熟悉算法的情况下，首先需要通过对题目的暴力求解的方式来解题，而然后通过暴力求解的小步骤看出有没有优化方案，在上面这到题中我们发现right每次都向前重置和sum每次重置是没有必要的，向上述两个指针一直向同一方向移动的操作，我们叫做滑动窗口。滑动窗口是双指针的一种，是两个指针的操作。

编写代码：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0 , right = 0;
        int sum = 0; // 记录窗口中所有数的和
        int len = 0; // 记录最短长度
        while(left < nums.size() && right < nums.size())
        {
            // 进窗口
            sum += nums[right];

            // 判断
            while(left < nums.size() && sum >= target)
            {
                // 更新答案
                if(len == 0)
                    len = right - left + 1;
                else
                    len = len > right - left + 1 ? right - left + 1 : len;

                // 出窗口
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return len;
    }
};

---

二、无重复字符的最长子串

题目描述：

思路讲解：
首先我们看到会想到暴力解法，就是将所有的子字符串全部列举出来，找到没有重复字符字符串返回其长度。

然后我们可以通过暴力解法的步骤可以发现可以使用滑动窗口进行求解，由于s由英文字母、数字、符号和空格组成，那么每个元素的范围一定在 [ 0 , 127 ] 这个范围，那么定义一个int hash[128] = {0}，来记录每个元素出现的次数，定义两个变量left = 0 ， right = 0，定义一个变量len记录最长重复字符字符串的长度，right 向后遍历

1. 当hash[s[right]] <= 1 时，使当前区间的长度与len进行比较，取大的值赋值给len，right 继续向后遍历。
2. 当 hash[s[right]] > 1 时，说明新添加的字符在原区间中存在，添加后就有重复字符，然后将left持续向后移动直到hash[s[right]] == 1停止，那么这段区间就没有重复元素，继续上面步骤1的操作。

当right遍历到字符串的末尾时结束循环，返回len完成本题。

编写代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0}; // 使用数组模拟哈希表
        int left = 0 , right = 0 ;
        int MaxLen = 0;
        while(right < s.size())
        {
            // 进窗口
            hash[s[right]]++;
            while(hash[s[right]] > 1)
            {
                // 出现相同元素则出窗口
                hash[s[left++]]--;
            }
            // 更新结果
            MaxLen = right - left + 1 > MaxLen ? right - left + 1 : MaxLen;
            right++;
        }
        return MaxLen;
    }
};

---

三、最大连续1的个数 III

题目描述：

思路讲解：
当我们看到这道题目的时候，可能真的会按照题目描述的那样将0赋值为1，但是后面会发现换一个区间时，还需要将转变后的1再变化0，那么这样操作起来会非常的困难，所以我们换一个思路，不将1转变，而是记录0的个数与k进行比较。

首先我们看到会想到暴力解法，就是将所有的子数组全部列举出来，找到子数组中0个数小于等于k的最长的子数组。

然后我们可以通过暴力解法的步骤可以发现可以使用滑动窗口进行求解，定义两个变量left = 0 ， right = 0，定义一个count记录区间中0的个数，定义一个变量len记录最长符合条件的数组长度，right 向后遍历

1. 当 count <= k 时，使当前区间的长度与len进行比较，取大的值赋值给len，right 继续向后遍历。
2. 当 count > k 时，说明区间内k次翻转不能将区间内所有的0转化为1，将left持续向后移动直到count <= k停止，继续上面步骤1的操作。

当right遍历到字符串的末尾时结束循环，返回len完成本题。

编写代码：

// 暴力求解超过时间限制
//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        int left = 0, right = 0;
//        int zeroCount = 0;
//        int numsLen = nums.size();
//        int MaxLen = 0;
//        while (left < numsLen)
//        {
//            right = left;
//            while (zeroCount <= k && right < numsLen)
//            {
//                if (nums[right++] == 0)
//                {
//                    zeroCount++;
//                }
//            }
//            if (nums[right - 1] == 1 || zeroCount <= k)
//                right++;
//            MaxLen = max(MaxLen, right - left - 1);
//            left++;
//            zeroCount = 0;
//        }
//        return MaxLen;
//    }
//};

// 滑动窗口
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int zeroCount = 0;  // 记录窗口中有多少个0
        int left = 0, right = 0;
        int numsLen = nums.size();
        int MaxLen = 0;     // 记录最长1的长度
        while (right < numsLen && zeroCount <= k)
        {
            // 当right指向的数字为0时，0的数量-1
            // 进窗口
            if (nums[right] == 0)
            {
                zeroCount++;
            }
            // 判断
            while (zeroCount > k)
            {
                // 出窗口
                // 当left指向的数字为0时，0的数量-1
                if (nums[left++] == 0)
                {
                    zeroCount--;
                }
            }
            // 更新结果
            MaxLen = max(MaxLen, right - left + 1);

            right++;
        }
        return MaxLen;
    }
};

---

四、将 x 减到 0 的最小操作数

题目描述：

思路讲解：

首先我们看到会想到暴力解法，定义一个变量sum记录整个数组元素的和，然后将所有的子数组全部列举出来，找到子数组中所有元素相加等于sum - x的最长子数组。

然后我们可以通过暴力解法的步骤可以发现可以使用滑动窗口进行求解，定义两个变量left = 0 ， right = 0，定义一个Pratsum记录区间中所有元素的和，定义一个变量len记录最长符合条件的数组长度，right 向后遍历

1. 当 Pratsum < sum - k 时，right 继续向后遍历。
2. 当 Pratsum == sum - k 时，使当前区间的长度与len进行比较，取大的值赋值给len，那么right向后移动必定没有符合条件的子数组，那么使left向后+1，那么Pratsum 必定小于 sum - k，继续上面操作1的步骤。
3. 当 Pratsum > sum - k 时，那么right向后移动必定没有符合条件的子数组，将left持续向后移动直到Pratsum == sum - k停止，满足上面哪个条件就进行哪一个步骤的操作。

当right遍历到字符串的末尾时结束循环，返回len完成本题。

编写代码：

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0, partSum = 0;
        int MinCount = INT_MAX;
        int numsLen = nums.size();
        for (auto e : nums)
        {
            sum += e;
        }

        int target = sum - x;
        // 说明不存在
        if (target < 0)
            return -1;

        if(target == 0)
            return numsLen;

        int  left = 0, right = 0;
        while (right < numsLen)
        {
            // 进窗口
            partSum += nums[right];

            // 判断
            while (left < right && target < partSum)
            {
                // 出窗口
                partSum -= nums[left++];
            }
 
            // 更新结果
            if (partSum == target)
            {
                MinCount = min(MinCount, numsLen - (right - left + 1));
            }
            right++;
        }
        if (MinCount == INT_MAX)
            return -1;

        return MinCount;
    }
};

---

五、水果成篮

题目描述：

思路讲解：
首先我们看到会想到暴力解法，就是将所有的子数组全部列举出来，找出其中元素只有两种的最长子数组。

然后我们可以通过暴力解法的步骤可以发现可以使用滑动窗口进行求解，定义一个unordered_map<int,int> um来记录区间中元素的种类和每种种类含有有多少个，定义两个变量left = 0 ， right = 0，定义一个count记录水果最大数目，right 向后遍历

1. 当 um.size() <= 2 时，使当前区间的长度与count进行比较，取大的值赋值给count，right 继续向后遍历。
2. 当um.size() > 2 时，那么map中元素种类超过2中，将left持续向后移动直到um.find(fruits[left])->second == 0（其中一个元素的个数为0）停止，并将这个元素从map中删除，继续上面步骤1的操作。

当right遍历到字符串的末尾时结束循环，返回count完成本题。

编写代码：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> um;
        int MaxCount = 0;            // 记录水果最大数目
        int left = 0 , right = 0;    
        int len = fruits.size();
        
        while(right < len)
        {
            // 进窗口
            um[fruits[right]]++;

            // 判断
            while(um.size() > 2)
            {
                // 出窗口
                um[fruits[left]]--;
                if(um.find(fruits[left])->second == 0)
                {
                    um.erase(fruits[left]);
                }
                left++;
            }

            MaxCount = max(right - left + 1,MaxCount);
            right++;
        }
        return MaxCount;
    }
};

---

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

题目描述：

思路讲解：
首先我们看到会想到暴力解法，就是将所有的子字符串全部列举出来，找出所有子字符串中元素出现的次数相同的子字符串，并记录其下标。

然后我们可以通过暴力解法的步骤可以发现可以使用滑动窗口进行求解，由于字符串s 和 p 仅包含小写字母，那么定义int hash1[26] = {0} , hash2[26] = {0}分别记录区间内元素及其元素的个数和字符串p的元素及其元素个数，定义两个变量left = 0 ， right = 0，定义一个vector<int> ans来记录答案，right 向后遍历

1. 当 right - light + 1 < pLen(字符串p长度) 时，right 继续向后遍历。
2. 当 right - light + 1 == pLen(字符串p长度) 时，遍历hash1和hash2，对比其中的元素及其元素个数是否相同，相同则将left存入ans中，然后left向后+1。

当right遍历到字符串的末尾时结束循环，返回ans完成本题。

编写代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 由于这里字符串中只有小写字母, a对应0,后面的以此类推
        int hash1[26] = {0} , hash2[26] = {0};
        int left = 0 , right = 0;
        int pos = 0;
        vector<int> ans;
        int sLen = s.size() , pLen = p.size();

        if(sLen < pLen)
            return ans;

        for(auto e : p)
        {
            hash2[e - 'a']++;
        }

        while(left <= sLen - pLen && right < sLen)
        {
            // 进窗口
            for(; right - left != pLen ; right++)
            {
                hash1[s[right] - 'a']++;
            }

            // 判断
            for(pos = 0 ; pos < 26 ; pos++)
            {
                if(hash1[pos] != hash2[pos])
                {
                    break;
                }
            }
            // 更新结果
            if(pos == 26)
            {
                ans.push_back(left);
            }

            // 出窗口
            hash1[s[left++] - 'a']--;
        }
        
        return ans;
    }
};

但是上面的思路有一个可以优化的点，就是每次匹配的时候就需要将hash1和hash2遍历一遍，其实可以转化一个思路，定义一个变量count记录有效元素的个数，新插入的元素在hash1的个数小于hash2对应的元素的个数则count+1，新删除的元素在hash1的个数小于等于hash2对应的元素的个数则count-1，当count == pLen时，那么符合条件则当前区间的子字符串是字符串p的异位词，将left存入ans。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 由于这里字符串中只有小写字母, a对应0,后面的以此类推
        int hash1[26] = {0} , hash2[26] = {0};
        int left = 0 , right = 0;
        int count = 0;   // 记录hash1中有效字符的个数
        vector<int> ans;
        int sLen = s.size() , pLen = p.size();

        if(sLen < pLen)
            return ans;

        for(auto e : p)
        {
            hash2[e - 'a']++;
        }

        while(right < sLen)
        {
            // 进窗口
            for(; right - left != pLen ; right++)
            {
                // 条件成立说明进窗口的字符为有效字符 
                if(hash1[s[right] - 'a'] < hash2[s[right] - 'a'])
                    count++;
                hash1[s[right] - 'a']++;
            }

            // 更新结果
            if(count == pLen)
                ans.push_back(left);

            // 出窗口
            // 条件成立说明出窗口的字符为有效字符
            if(hash1[s[left] - 'a'] <= hash2[s[left] - 'a'])
                count--;

            hash1[s[left++] - 'a']--;
        }
        
        return ans;
    }
};

---

七、串联所有单词的子串

题目描述：

思路讲解：
首先我们看到会想到暴力解法，找到word中的所有字符串的组合方式，找到s中所有与word组合出来的字符串相同的子字符串的下标并返回。

首先使用滑动窗口对找到s的子串进行优化，然后我们会发现两个字符串的比较非常低效，那么换一个方式，定义一个哈希表unordered_map<string,int> umWord，记录word中所有字符串和字符串的次数，然后按照word中每个字符串的长度将s进行分割，再定义一个哈希表unordered_map<string,int> umS，记录分割后s子字符串和子字符串出现的次数，定义umWordsCount记录umWord中元素的个数，定义umSCount记录umS中元素的个数。定义一个count记录有效元素个数，切割后s的子串插入umS中时，若当前元素在umS中比umWord少时，则当前元素为有效元素。

然后使用滑动窗口进行优化，定义一个变量wordsLen记录word中元素的长度，定义一个变量pos，left的范围为[ 0 , wordsLen - 1 ]，定义两个变量left = pos ， right = pos，right 向后遍历，每次移动wordsLen个长度，定义一个vector<int> ans记录答案。

1. 当 umSCount <= umWordsCount 时，使 count 与 word 的元素个数进行比较，若相等则将 left 存入 ans 中，right 向后遍历，移动wordsLen个长度，并将新的字符串加入到 umS中，若当前元素在umS中比umWord少时，则当前元素为有效元素，更新有效元素个数加一。

2. 当 umSCount > umWordsCount 时，若s中[ left ，left + wordsLen - 1 ] 上的子字符串在umS中比umWord少或相等时，则当前元素为有效元素，更新有效元素个数减一，然后使从[ left ，left + wordsLen - 1 ] 上的子字符串在umS中的个数减一，若个数本就为1，则将它从umS中移除，left 向后遍历，然后移动wordsLen个长度，那么umSCount 和 umWordsCount 的关系必定满足umSCount == umWordsCount，继续上面步骤1的操作。

我们需要遍历pos遍上面的循环，当pos == wordsLen - 1 并且 right遍历到最后结束循环，返回ans完成本题。

编写代码：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> umWord;
        unordered_map<string,int> umS;
        vector<int> ans;
        int sLen = s.size();             // s的长度
        int wordsLen = words[0].size();  // word中每个元素的长度
        int wordsCount = words.size();   // words的长度
        int umWordsCount = words.size();   //记录umWord中有多少个元素
        int count = 0;  // 记录窗口中有效元素的个数
        int umSCount = 0;  // 记录umS中有多少个元素
        for(auto str : words)
        {
            umWord[str]++;
        }

        for(int pos = 0 ; pos < wordsLen ; pos++)
        {
            for(int left = pos , right = pos; 
                right < sLen - wordsLen + 1; right += wordsLen)
            {
                // 进窗口
                string tmp1(s.begin() + right , s.begin() + right + wordsLen);
                // count() 方法只需检查指定元素在哈希表中的出现次数，而不需要返回实际的值。
                // 使用 [] 操作符时，如果元素不存在，通常需要进行额外的查找操作以确定元素是否存在，
                // 并且在哈希表中查找该元素所需的时间取决于哈希表的大小和元素的散列值。
                // 这可能导致性能损失，尤其是在哈希表很大或哈希函数不够高效时。
                if(umWord.count(tmp1) && umS[tmp1] < umWord[tmp1])
                    count++;

                umSCount++;
                umS[tmp1]++;

                // 判断
                if(umSCount > umWordsCount)
                {
                    // 出窗口
                    string tmp2(s.begin() + left , s.begin() + left + wordsLen);
                    
                    if(umWord.count(tmp2) && umS[tmp2] <= umWord[tmp2])
                        count--;
                    
                    umS[tmp2]--;
                    umSCount--;

                    if(umS[tmp2] == 0)
                        umS.erase(tmp2);

                    left += wordsLen;
                }

                // 更新结果
                if(count == wordsCount)
                    ans.push_back(left);
            }
            count = 0;
            umS.clear();
            umSCount = 0;
        }
        return ans;
    }   
};

---

八、最小覆盖子串

题目描述：

思路讲解：
首先我们看到会想到暴力解法，找到s中所有的子字符串，再与t进行对比，找到最短的符合条件的子字符串。

然后我们可以通过暴力解法的步骤可以发现可以使用滑动窗口进行求解，定义tType 记录字符串t中有多少种元素，定义一个 count 记录字符串中s对应字符串中有效元素种类的个数，定义一个 ansLen 记录最短子字符串的长度，定义一个 begin 记录最短子字符串的开始，由于字符串s和t都是由字母组成，定义int hash1['z' - 'A' + 1] = {0} 和 int hash2['z' - 'A' + 1] = {0}，分别滑动窗口s和字符串t记录t中元素和元素出现的次数，定义两个变量 left = 0 ， right = 0，right 向后遍历

1. 当 count < tType 时，right 向后移动，滑动窗口中新增元素，若增加后该元素对应在hash1 和 hash2中的个数相同，则为有效元素，count++。
2. 当 count == tType 时，使当前区间的长度与ansLen进行比较，取大的值赋值给ansLen，left 继续向后遍历，滑动窗口中删除元素，若删除的元素对应在hash1 和 hash2中的个数相同，则为有效元素，count--，直到count < tType。
3. 由于count == tType就会开始删除元素，所以这里不好出现count > tType的情况。

当right遍历到字符串的末尾时结束循环，截取字符串s中从begin位置开始长度为ansLen长度的子字符串返回，即可完成本题。

编写代码：

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0 , right = 0;
        int sLen = s.size();
        int tType = 0; // 记录字符串t中有多少种元素
        int count = 0; // 记录字符串中s对应字符串中有效元素种类的个数
        int hash1['z' - 'A' + 1] = {0};
        int hash2['z' - 'A' + 1] = {0};
        int ansLen = INT_MAX;
        int begin = -1; // 优化
        // string ans;  不需要每次找到最短子串就赋值

        for(auto e : t)
            // 插入之前没有这个元素，插入后种类加一
            if(hash2[e - 'A']++ == 0)
                tType++;

        while(right < sLen)
        {
            int tmpRight = s[right] - 'A';
            // 进窗口
            hash1[tmpRight]++;
            if(hash1[tmpRight] == hash2[tmpRight])
                count++;

            int tmpLeft = s[left] - 'A';
            // 判断
            while(count == tType || 
                (s[left] == s[left+1] && hash1[tmpLeft] > hash2[tmpLeft]))
                // 防止出现连续相同的无效字符
            {
                // 更新结果
                tmpLeft = s[left] - 'A';

                // 取最小子串
                if(count == tType && ansLen > right - left + 1)
                {
                    ansLen = right - left + 1;
                    // 优化前
                    // ans = s.substr(left , ansLen);
                    begin = left;
                }

                // 出窗口
                if(hash1[tmpLeft] == hash2[tmpLeft])
                    count--;
                
                hash1[tmpLeft]--;
                left++;
            }
            right++;
        }

        if(begin == -1)
            return "";
        else 
            return s.substr(begin , ansLen);
    }
};

---

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹

原文地址：https://blog.csdn.net/qq_55401402/article/details/137244867

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！