算法剖析：滑动窗口

文章目录

• 前言
• 一、长度最小的子数组
• 二、无重复字符的最长子串
• 三、最大连续1的个数 III
• 四、将 x 减到 0 的最小操作数
• 五、水果成篮
• 六、找到字符串中所有字母异位词
• 七、串联所有单词的子串
• 八、最小覆盖子串
• 总结

---

前言

滑动窗口可以看作为一种特殊的通向双指针，这两个指针所维护的区域就像一个窗口一样不断滑动，看似嵌套了两个循环，实则只进行了一次遍历，规避掉了很多无用的遍历，时间复杂度为O（n）。

基本思路是这样的~

---

一、长度最小的子数组

长度最小的子数组

1. 初始化左右指针：

   • left = 0, right = 0：两个指针都从数组的起点开始，表示窗口的左右边界。
   • 初始窗口内的和 sum = 0。

2. 窗口扩展：

   • 通过移动右指针将右边的元素加入窗口（即增大窗口）。每次加入元素后，更新窗口内的和 sum。
   • 如果窗口内元素的和 sum 大于或等于目标值 target，此时更新最短长度，并考虑收缩窗口。

3. 窗口收缩：

   • 当窗口内的和满足条件时，通过移动左指针将左边的元素移出窗口（即缩小窗口），继续检查新的窗口是否仍满足条件。
   • 如果依然满足条件，就继续更新最短长度。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int left = 0, right = 0, sum = 0, len = INT_MAX;

        while(right < nums.size())
        {
            sum += nums[right++];
            while(sum >= target)
            {
                sum -= nums[left++];
                len = min(len, right - left + 1);
            }
        }

        return len == INT_MAX? 0 : len;
    }
};

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

无重复字符的最长子串

滑动窗口需要满足条件：窗口内的所有元素都不重复。

具体做法如下：

• 当右端元素 ch 进入窗口时，使用哈希表统计该字符的出现频率。
  • 如果该字符的频次超过 1，表示窗口内出现了重复元素，此时需要从左侧开始缩小窗口，直到该字符的频次恢复为 1，确保窗口内没有重复元素，再更新结果。
  • 如果字符频次不超过 1，说明窗口内没有重复元素，直接更新结果。

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

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

---

三、最大连续1的个数 III

最大连续1的个数 III

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int left = 0, right = 0, ret = 0, count = 0;
        while(right < nums.size())
        {
            if(nums[right] == 0 )
                count++;

            while(count > k)
            {
                if(nums[left++] == 0)
                    count--;
            }
            
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};

---

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

将 x 减到 0 的最小操作数

这道题用到了正难则反的思想，求左右两边的和等于 X 太难了，而且他的区间不连续，我们可以求中间连续的区间，使他的和等于sum - x 并且长度最大。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int sum = 0, target, n = nums.size();
        for(auto e : nums) sum += e;

        target = sum - x;
        if(target < 0) return -1;

        int left = 0, right = 0;
        int tmp = 0, ret = -1;
        while(right < n)
        {
            tmp += nums[right];

            while(tmp > target)
                tmp -= nums[left++];

            if(tmp == target) ret = max(ret, right - left + 1);

            right++;
        }

        return ret == -1 ? -1 : n - ret;
    }
};

---

五、水果成篮

水果成篮

可以把这个问题看作在一个数组中寻找最多包含两种不同元素的最长子数组。使用滑动窗口的思路，移动右指针扩大窗口，统计水果种类数。当种类超过两种时，移动左指针缩小窗口，直到只剩两种水果为止。每次窗口内符合条件时，更新最长长度的结果。

class Solution {
public:
    int totalFruit(vector<int>& f) 
    {
        int hash[100001] = {0}, ret = 0;
        for(int left = 0, right = 0, kinds = 0; right < f.size(); right++)
        {
            if(hash[f[right]] == 0) kinds++;
            hash[f[right]]++;

            while(kinds > 2)
            {
                hash[f[left]]--;
                if(hash[f[left]] == 0) kinds--;
                left++;
            }

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

        return ret;
    }
};

---

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

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

这段代码实现了寻找字符串 s 中所有字母异位词 p 的子串的起始索引。具体思路如下：

主要思路

1. 字符频率统计：

   • 使用两个大小为 26 的数组 hash1 和 hash2 来记录字符的频率。hash1 用于统计当前滑动窗口内的字符频率，而 hash2 用于记录字符串 p 的字符频率。

2. 初始化频率数组：

   • 遍历字符串 p，将每个字符的频率存储到 hash2 中。

3. 滑动窗口：

   • 使用两个指针 left 和 right 来表示当前窗口的范围：
     • right 用于遍历字符串 s，逐步扩大窗口。
     • left 用于在窗口内调整左边界，确保窗口的大小不超过 p 的大小。
   • 当窗口内的字符数超过 p 的长度时，通过移动 left 来缩小窗口，并更新相应字符的频率。

4. 检查异位词：

   • 在每次扩展窗口后，调用 check 函数来比较 hash1 和 hash2。如果它们相等，说明当前窗口内的字符是 p 的一个异位词，将 left 的值添加到结果 ret 中。

class Solution {
public:

    bool check(int* hash1, int* hash2)
    {
        for(int i = 0; i < 26; i++)
        {
            if(hash1[i] != hash2[i])
                return false;
        }

        return true;
    }

    vector<int> findAnagrams(string s, string p) 
    {
        int hash1[26] = {0};
        int hash2[26] = {0};
        int n = p.size();

        for(int i = 0; i < n; i++)
        {
            hash2[p[i] - 'a']++;
        }

        vector<int> ret;
        for(int left = 0, right = 0; right < s.size(); right++)
        {   
            hash1[s[right] - 'a']++;

            if(right - left + 1 > p.size())
                hash1[s[left++] - 'a']--;

            if(check(hash1, hash2))
                ret.push_back(left);
            
        }

        return ret;
    }
};

---

此方案的优化：

这段代码通过优化滑动窗口的方法来高效地查找字符串 s 中的所有字母异位词 p 的起始索引，具体的优化点如下：

1. 使用单一频率数组：

   • 原来的方法使用两个频率数组 hash1 和 hash2，分别用于存储字符串 p 和当前滑动窗口中字符的频率。优化后的方法仍然保留这两个数组，但通过增加 count 变量来简化比较过程。

2. 维护一个计数变量：

   • 使用 count 变量来记录当前窗口中符合 p 中字符频率要求的字符个数。每当 hash2 中某个字符的频率在窗口中更新后，如果该字符的频率小于等于 hash1 中的频率，则 count 增加；反之则减少。这样，程序只需检查 count 是否等于 m（p 的长度）来确定当前窗口是否为一个异位词，而不必逐个比较两个频率数组。

3. 窗口维护：

   • 当窗口的大小超过 p 的长度时，使用 left 指针移出字符，同时更新 hash2 和 count。如果字符的频率变为小于等于 hash1 对应字符的频率，则减少 count。

优化效果

• 时间复杂度：
  • 该方法的时间复杂度为 O(n)，其中 n 是字符串 s 的长度。相比于可能需要每次进行完整的频率数组比较，减少了不必要的比较操作。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int hash1[26] = {0}; // 统计字符串 p 中每个字符出现的个数
        for (auto ch : p)
            hash1[ch - 'a']++;
        int hash2[26] = {0}; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
        int m = p.size();
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            // 进窗⼝ + 维护 count
            if (++hash2[in - 'a'] <= hash1[in - 'a'])
                count++;

            // 判断
            if (right - left + 1 > m) {
                char out = s[left++];
                // 出窗⼝ + 维护 count
                if (hash2[out - 'a']-- <= hash1[out - 'a'])
                    count--;
            }
            // 更新结果
            if (count == m)
                ret.push_back(left);
        }
        return ret;
    }
};

---

七、串联所有单词的子串

串联所有单词的子串

这道题是对上一道题的升级，目标是找到字符串 s 中所有由给定单词列表 words 中单词构成的连续子串的起始索引。与之前的字母异位词问题相比，新的问题增加了以下几个方面的复杂性和实现细节：

主要区别

1. 多单词匹配：

   • 之前的题目只关注一个单词的异位词，而这道题需要同时匹配多个单词的组合，这就需要处理频率统计和窗口移动的逻辑。

2. 使用 unordered_map：

   • 在这道题中，使用 unordered_map<string, int> 来存储单词频率，方便快速查找每个单词的出现次数和进行更新。这与使用固定大小数组的方法不同，更加灵活。

3. 动态窗口：

   • 窗口的移动方式有所不同。在处理 s 的每个位置时，当前单词的长度为 len，窗口的移动步长也为 len。这保证了每次滑动都是按照单词的边界进行的。

实现过程

1. 初始化：

   • 使用 hash1 来保存单词列表 words 中每个单词的频率。
   • len 代表每个单词的长度，m 代表单词的数量。

2. 滑动窗口：

   • 外层循环执行 len 次，以处理不同的起始点。这是为了确保即使字符串 s 中的单词拼接是错开的（例如，s 开始于第二个单词的部分），也能被匹配到。
   • 内层循环则通过 left 和 right 指针维护当前窗口内的单词频率。right 每次增加 len，即逐个检查每个单词。

3. 进出窗口逻辑：

   • 当新的单词进入窗口时，更新 hash2 并检查其是否在 hash1 中，并确保频率不超过所需频率（count 变量的管理）。
   • 当窗口的大小超过了 len * m（即所有单词的长度之和），就需要从左边移出一个单词，并更新 hash2 和 count。

4. 结果更新：

   • 通过检查 count 是否等于 m 来判断当前窗口是否包含了所有单词的组合，如果是，则将 left 添加到结果中。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
        for (auto& s : words)
            hash1[s]++;
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) // 执⾏ len 次
        {
            unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
            for (int left = i, right = i, count = 0; right + len <= s.size();
                 right += len) {
                // 进窗⼝ + 维护 count
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in])
                    count++;
                // 判断
                if (right - left + 1 > len * m) {
                    // 出窗⼝ + 维护 count
                    string out = s.substr(left, len);
                    if (hash1.count(out) && hash2[out] <= hash1[out])
                        count--;
                    hash2[out]--;
                    left += len;
                }
                // 更新结果
                if (count == m)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};

---

八、最小覆盖子串

最小覆盖子串

解法（滑动窗口 + 哈希表）

算法思路：

• 研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。
• 如何判断当前窗口内的所有字符是否符合要求？我们可以使用两个哈希表，其中一个统计目标串的信息，另一个动态维护窗口内字符串的信息。
• 当动态哈希表中包含目标串中所有的字符，并且对应的个数都不少于目标串的哈希表中各个字符的个数时，当前的窗口就是一种可行的方案。

算法流程：

1. 定义两个全局的哈希表：

   • 1号哈希表 hash1 用来记录目标串 t 的信息。
   • 2号哈希表 hash2 用来记录当前窗口内的子串信息。

2. 实现一个接口函数，判断当前窗口是否满足要求：

   • 遍历两个哈希表中对应位置的元素：
     • 如果 t 中某个字符的数量大于窗口中字符的数量（即2号哈希表某个位置大于1号哈希表），则说明不匹配，返回 false。
     • 如果全都匹配，返回 true。

主函数中：

1. 先将 t 的信息放入2号哈希表中。

2. 初始化一些变量：

   • 左右指针：left = 0，right = 0；
   • 目标子串的长度：minlen = INT_MAX；
   • 目标子串的起始位置：begin = -1（通过目标子串的起始位置和长度，可以找到结果）。

3. 当 right 小于字符串 s 的长度时，进行以下循环：

   • 将当前遍历到的元素加入1号哈希表中；
   • 检测当前窗口是否满足条件：
     • 如果满足条件：
       • 判断当前窗口是否变小。如果变小，更新长度 minlen 和字符串的起始位置 begin；
       • 判断完毕后，将左侧元素滑出窗口，同时更新1号哈希表；
       • 重复上述两个过程，直到窗口不满足条件；
   • right++，遍历下一个元素。

4. 判断 begin 是否为 -1：

   • 如果相等，说明没有匹配，返回空串；
   • 如果不相等，说明匹配，返回 s 中从 begin 位置往后 minlen 长度的字符串。

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0}; // 统计字符串 t 中每⼀个字符的频次
        int kinds = 0;        // 统计有效字符有多少种
        for (auto ch : t)
            if (hash1[ch]++ == 0)
                kinds++;
        int hash2[128] = {0}; // 统计窗⼝内每个字符的频次
        int minlen = INT_MAX, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in])
                count++;           // 进窗⼝ + 维护 count
            while (count == kinds) // 判断条件
            {
                if (right - left + 1 < minlen) // 更新结果
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out])
                    count--; // 出窗⼝ + 维护 count
            }
        }
        if (begin == -1)
            return "";
        else
            return s.substr(begin, minlen);
    }
};

---

总结

到这里，我们滑动窗口的内容就结束啦~
谢谢大家！