探索算法系列 - 滑动窗口

长度最小的子数组（原题链接）

给定一个含有

n

** **个正整数的数组和一个正整数

target

** 。**

找出该数组中满足其总和大于等于** **

target

** **的长度最小的 子数组

并返回其长度。如果不存在符合条件的子数组，返回

0

。

解题思路

1. 滑动窗口：使用滑动窗口的方法，通过两个指针 left 和 right 来表示窗口的左右边界，用于寻找满足条件的子数组。
2. 动态调整窗口大小：通过移动 right 指针扩展窗口，直到窗口内的元素和大于或等于目标值 target，然后移动 left 指针收缩窗口，以便找到满足条件的最短子数组。
3. 最小长度：在每次窗口满足条件时，更新最小子数组长度。

步骤说明

1. 初始化：- 变量 n 用来保存数组 nums 的长度。- 变量 sum 用来保存当前窗口内的元素和。- 变量 len 用来保存满足条件的最短子数组的长度，初始值为 INT_MAX 表示无穷大。- 两个指针 left 和 right 都初始化为 0，表示窗口的左右边界。
2. 遍历数组：- 使用 for 循环遍历数组，right 指针从 0 到 n-1。- 每次将当前元素 nums[right] 加到 sum 中，扩展窗口的右边界。
3. 收缩窗口：- 使用 while 循环检查当前窗口内的元素和 sum 是否大于或等于目标值 target。- 如果满足条件，更新最短子数组长度 len 为当前窗口长度 right - left + 1 和之前的最小长度之间的较小值。- 将窗口左边界元素 nums[left] 从 sum 中减去，并将 left 指针右移，收缩窗口的左边界。
4. 返回结果：- 如果 len 仍然是 INT_MAX，表示没有找到满足条件的子数组，返回 0。- 否则，返回 len。

具体代码

class Solution 
{
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int n = nums.size(); // 数组长度
        int sum = 0; // 当前窗口内元素的总和
        int len = INT_MAX; // 记录最短子数组的长度，初始值为最大整数
        
        for (int left = 0, right = 0; right < n; right++)
        {
            sum += nums[right]; // 进窗口，更新总和
            
            while (sum >= target) // 如果窗口内总和满足条件，尝试收缩窗口
            {
                len = min(len, right - left + 1); // 更新最短子数组的长度
                sum -= nums[left]; // 移动左边界，减少总和
                left++;
            }
        }
        
        return len == INT_MAX ? 0 : len; // 如果未找到满足条件的子数组，返回 0，否则返回最短子数组长度
    }
};

无重复字符的最长子串（原题链接）

给定一个字符串

s

，请你找出其中不含有重复字符的 最长子串 的长度。

解题思路

1. 滑动窗口：使用滑动窗口的方法，通过两个指针 left 和 right 来表示窗口的左右边界，用于寻找最长的无重复字符子串。
2. 哈希数组：使用哈希数组 hash 记录每个字符在当前窗口内出现的次数。
3. 动态调整窗口大小：通过移动 right 指针扩展窗口，直到窗口内有重复字符，然后移动 left 指针收缩窗口，以便保持窗口内的字符都是唯一的。
4. 最大长度：在每次窗口内没有重复字符时，更新最长子串的长度。

步骤说明

1. 初始化：- 变量 hash 用来记录每个字符在当前窗口内出现的次数，大小为128（因为ASCII字符一共128个）。- 变量 left 和 right 初始化为 0，表示窗口的左右边界。- 变量 n 用来保存字符串 s 的长度。- 变量 ret 用来保存最长无重复字符子串的长度，初始值为 0。
2. 遍历字符串：- 使用 while 循环遍历字符串，当 right 小于 n 时进行循环。- 每次将当前字符 s[right] 在 hash 中的值加1，扩展窗口的右边界。
3. 收缩窗口：- 使用 while 循环检查当前窗口内的字符 s[right] 是否出现多次。- 如果出现多次，则将窗口左边界字符 s[left] 在 hash 中的值减1，并将 left 指针右移，收缩窗口的左边界，直到窗口内字符都是唯一的。
4. 更新最大长度：- 在每次窗口内字符都是唯一时，更新最长子串的长度 ret 为当前窗口长度 right - left + 1 和之前的最大长度之间的较大值。
5. 返回结果：- 返回 ret，即最长无重复字符子串的长度。

具体代码

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int hash[128] = { 0 }; // 记录字符的频次
        int left = 0, right = 0, n = s.size(); // 初始化左右边界和字符串长度
        int ret = 0; // 记录最长子字符串的长度
        
        while (right < n)
        {
            hash[s[right]]++; // 进窗口，更新当前字符的频次
            while (hash[s[right]] > 1) // 如果窗口内有重复字符，收缩窗口
                hash[s[left++]]--; // 移动左边界，并更新频次
            
            ret = max(ret, right - left + 1); // 更新结果
            right++; // 移动右边界
        }
        
        return ret; // 返回最长不包含重复字符的子字符串长度
    }
};

最大连续1的个数 III（原题链接）

给定一个二进制数组

nums

和一个整数

k

，如果可以翻转最多

k

个

0

，则返回 *数组中连续

1

的最大个数* 。

解题思路

1. 滑动窗口：使用滑动窗口的方法，通过两个指针 left 和 right 来表示窗口的左右边界，用于寻找包含最多 k 个 0 的最长连续子数组。
2. 计数器：使用变量 zero 记录当前窗口内 0 的数量。
3. 动态调整窗口大小：通过移动 right 指针扩展窗口，直到窗口内的 0 的数量超过 k，然后移动 left 指针收缩窗口，以便保持窗口内的 0 的数量不超过 k。
4. 最大长度：在每次窗口内的 0 的数量不超过 k 时，更新最长子数组的长度。

步骤说明

1. 初始化：- 变量 ret 用来保存包含最多 k 个 0 的最长连续子数组的长度，初始值为 0。- 变量 left 和 right 初始化为 0，表示窗口的左右边界。- 变量 zero 用来记录当前窗口内 0 的数量，初始值为 0。
2. 遍历数组：- 使用 for 循环遍历数组，right 指针从 0 到 nums.size()-1。- 每次将当前元素 nums[right] 加到窗口中，如果是 0，则 zero 加1。
3. 收缩窗口：- 使用 while 循环检查当前窗口内的 0 的数量 zero 是否超过 k。- 如果超过 k，则将窗口左边界元素 nums[left] 从窗口中移出，并将 left 指针右移，如果移出的元素是 0，则 zero 减1。
4. 更新最大长度：- 在每次窗口内的 0 的数量不超过 k 时，更新最长子数组的长度 ret 为当前窗口长度 right - left + 1 和之前的最大长度之间的较大值。
5. 返回结果：- 返回 ret，即包含最多 k 个 0 的最长连续子数组的长度。

具体代码

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++)
        {
            if(nums[right] == 0) // 进窗口
                zero++;
            while(zero > k) // 如果窗口中的0数量超过k，收缩窗口
            {
                if(nums[left++] == 0) // 移动左边界
                {
                    zero--;
                }
            }
            ret = max(ret, right - left + 1); // 更新结果
        }
        return ret; // 返回结果
    }
};

将 x 减到 0 的最小操作数（原题链接）

给你一个整数数组

nums

和一个整数

x

。每一次操作时，你应当移除数组

nums

最左边或最右边的元素，然后从

x

中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将

x

恰好 减到

0

，返回** 最小操作数 **；否则，返回

-1

。

解题思路

• 定义变量 sum 计算数组中所有元素的总和，然后定义目标值 target 为 sum - x。
• 使用滑动窗口的方法找到最长的子数组，其和为 target。
• 最终结果是 nums.size() - ret，即数组的长度减去最长子数组的长度。

步骤说明

1. 初始化：- 计算数组 nums 所有元素的总和 sum。- 计算目标值 target 为 sum - x。- 如果 target < 0，返回 -1，因为不可能找到和为负数的子数组。
2. 定义变量：- ret 初始化为 -1，用于存储找到的最长子数组的长度。- left 和 right 分别为滑动窗口的左右边界，初始化为 0。- tmp 为当前滑动窗口内的元素和，初始化为 0。
3. 滑动窗口：- 遍历数组 nums，right 从 0 到 nums.size()。- 将 nums[right] 加到 tmp 中，表示右边界扩展。- 如果 tmp 大于 target，不断将 nums[left] 减去 tmp 中，并将 left 右移，表示左边界收缩。- 如果 tmp 等于 target，更新 ret 为当前窗口长度，即 right - left + 1。
4. 结果返回：- 如果 ret 仍然是 -1，返回 -1，表示没有找到满足条件的子数组。- 否则返回 nums.size() - ret，即操作次数。

具体代码

class Solution
{
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int sum = 0;
        for(int a : nums) sum += a; // 计算数组的总和
        int target = sum - x; // 计算需要找到的子数组和
        if(target < 0) return -1; // 如果目标和小于0，返回-1

        int ret = -1; // 记录最长子数组长度
        for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
        {
            tmp += nums[right]; // 进窗口，更新当前和
            while(tmp > target) // 如果当前和超过目标，收缩窗口
                tmp -= nums[left++]; 
            if(tmp == target) // 如果当前和等于目标，更新最长子数组长度
                ret = max(ret, right - left + 1);
        }
        if(ret == -1) // 如果没有找到符合条件的子数组，返回-1
            return ret;
        else 
            return nums.size() - ret; // 返回移除的元素数量
    }
};

水果成篮（原题链接）

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组

fruits

表示，其中

fruits[i]

是第

i

棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组

fruits

，返回你可以收集的水果的 最大 数目。

解题思路

目的是在一个数组

f

中找到包含两种不同元素的最长子数组。该问题可以被视为一个“滑动窗口”问题，通过使用滑动窗口的方法保持一个窗口，使得窗口内最多包含两种不同的元素。

步骤说明

1. 初始化：- 定义一个哈希数组 hash，用于记录每个元素出现的次数，大小为 100001，初始值都为 0。- 定义变量 ret，用于记录最长子数组的长度，初始值为 0。- 定义滑动窗口的左右边界 left 和 right，初始值为 0。- 定义变量 kinds，用于记录窗口内不同元素的种类数，初始值为 0。
2. 滑动窗口：- 遍历数组 f，右边界 right 从 0 到 f.size()： - 如果 hash[f[right]] 为 0，说明这是一个新种类，kinds 增加 1。- 将当前元素 f[right] 的计数加 1。- 如果 kinds 大于 2，说明窗口内的不同元素超过两种，需要收缩左边界： - 将 f[left] 的计数减 1。- 如果 hash[f[left]] 为 0，说明这个种类已经完全移出窗口，kinds 减少 1。- 左边界 left 右移。- 更新 ret 为当前窗口的最大长度，即 right - left + 1。
3. 返回结果：- 返回 ret，即找到的最长子数组的长度。

具体代码

class Solution
{
public:
    int totalFruit(vector<int>& f)
    {
        int hash[100001] = { 0 }; // 记录每种水果的频次
        int 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

，找到

s

** **中所有

p

** **的 **异位词 **的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

**异位词 **指由相同字母重排列形成的字符串（包括相同的字符串）。

解题思路

目标是找到字符串

s

中所有与字符串

p

具有相同字符的排列（即找出所有的字母异位词）。该问题可以使用滑动窗口的方法来解决。我们使用两个哈希数组分别记录

p

的字符频率和当前窗口中字符的频率，然后通过滑动窗口来找到符合条件的子串。

步骤说明

1. 初始化：- hash1 用于记录字符串 p 中每个字符的频率。- hash2 用于记录当前滑动窗口中每个字符的频率。- m 为字符串 p 的长度，用于确定窗口大小。- ret 用于存储结果，即符合条件的起始位置。
2. **初始化 hash1**：- 遍历字符串 p，更新 hash1 中每个字符的频率。
3. 滑动窗口：- right 从 0 到 s.size() 遍历字符串 s，扩展窗口右边界。- 更新 hash2 中当前字符的频率，并根据字符频率更新计数器 count。- 如果当前窗口大小超过了 m，收缩左边界： - 更新 hash2 中移出字符的频率，并调整 count。- 如果 count 等于 m，说明当前窗口中的字符排列符合要求，将左边界的索引加入结果 ret。
4. 返回结果：- 返回结果 ret，包含所有符合条件的起始位置。

具体代码

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']++; // 更新 hash1
        
        int hash2[26] = { 0 }; // 记录当前窗口中每个字符的频率
        int m = p.size(); // 字符串 p 的长度
        
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            if (++hash2[in - 'a'] <= hash1[in - 'a'])
                count++; // 更新字符计数
            
            if (right - left + 1 > m) // 如果当前窗口大小超过 m，收缩窗口
            {
                char out = s[left++];
                if (hash2[out - 'a']-- < hash1[out - 'a'])
                    count--; // 更新字符计数
            }
            
            if (count == m) // 如果计数等于 m，说明窗口中的字符排列符合要求
                ret.push_back(left); // 记录结果
        }
        
        return ret; // 返回结果
    }
};

串联所有单词的子串（原题链接）

给定一个字符串

s

** **和一个字符串数组

words

。

words

中所有字符串 长度相同。

s

** **中的 串联子串 是指一个包含

words

中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在

s

** **中的开始索引。你可以以 任意顺序 返回答案。

解题思路

目的是找到字符串

s

中所有包含

words

中所有单词的子串的位置，其中每个单词的长度相同，并且每个单词的出现次数也与

words

中的出现次数一致。该问题可以使用滑动窗口的方法解决，通过尝试所有可能的起始位置，并维护一个窗口来检查包含的单词是否符合条件。

步骤说明

1. 初始化：- hash1 用于记录 words 中每个单词的频次。- len 为每个单词的长度。- m 为单词的总数。
2. 滑动窗口的起始位置：- 遍历 i 从 0 到 len-1，尝试所有可能的起始位置。
3. 维护窗口：- 定义 hash2 用于记录当前窗口中每个单词的频次。- 初始化左右边界 left 和 right，并设置 count 用于记录窗口中符合条件的单词数。- 右边界 right 从 i 开始，按单词长度递增，确保窗口内的单词都是长度一致的。
4. 进出窗口操作：- 进窗口： - 提取当前右边界的单词 in，更新 hash2 中的频次，并根据 hash1 更新 count。- 出窗口： - 如果窗口大小超过 len * m，移除左边界的单词 out，更新 hash2 和 count，并移动左边界。- 更新结果： - 如果 count 等于 m，说明窗口中包含的单词与 words 中的单词完全匹配，记录左边界的索引。
5. 返回结果：- 返回记录的结果 ret，包含所有符合条件的起始位置。

具体代码

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]++; // 初始化 hash1
        
        int len = words[0].size(); // 单词长度
        int m = words.size(); // 单词总数
        
        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) {
                // 进窗口 + 维护 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; // 返回结果
    }
};

最小覆盖子串（原题链接）

给你一个字符串

s

、一个字符串

t

。返回

s

中涵盖

t

所有字符的最小子串。如果

s

中不存在涵盖

t

所有字符的子串，则返回空字符串

""

。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

解题思路

目的是找到字符串

s

中包含字符串

t

的所有字符（包括重复字符）的最小子串。这个问题可以使用滑动窗口方法来高效解决。通过维护一个窗口来记录当前子串的字符频率，并确保窗口包含

t

中的所有字符，最终找到符合条件的最小子串。

步骤说明

1. 初始化：- hash1 用于记录字符串 t 中每个字符的频次。- kinds 记录 t 中有效字符的种类数（即有多少种不同的字符）。- hash2 用于记录当前窗口中每个字符的频次。- minlen 和 begin 用于记录最小子串的长度和起始位置，初始化为无效值。
2. 记录 t 中的字符频次：- 遍历字符串 t，更新 hash1 并记录有效字符的种类数 kinds。
3. 滑动窗口：- right 从 0 到 s.size()，遍历字符串 s： - 将当前右边界的字符加入窗口，更新 hash2 和 count（记录符合条件的字符种类数）。- 判断窗口是否符合条件： - 当窗口内的字符种类数等于 kinds 时，窗口符合条件。- 更新 minlen 和 begin，记录最小子串的长度和起始位置。- 收缩窗口： - 移动左边界 left，更新 hash2 和 count，直到窗口不再符合条件。
4. 返回结果：- 根据 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); // 返回最小子串
    }
};