文章目录
- 什么是滑动窗口?
- 经典题型分析与讲解
- **1. 长度最小的子数组**
- **2. 无重复字符的最长子串**
- **3. 最长重复子数组**
- **4. 将x减到0的最小操作数**
- 5. 水果成篮 (LeetCode 904)
- 6. 滑动窗口最大值 (LeetCode 239)
- 7. 字符串中的所有字母异位词 (LeetCode 剑指 Offer II 015)
- 8. 串联所有单词的子串 (LeetCode 30)
- 9. 最小覆盖子串 (LeetCode 76)
- 总结
在算法设计中,滑动窗口是一种高效的技巧,尤其在处理连续子数组或子串问题时非常有用。滑动窗口的核心思想是使用两个指针,定义一个范围,在这个范围内计算所需的值,然后根据问题的要求移动窗口的边界。本文将详细剖析几道经典题目,结合代码来讲解滑动窗口的原理和应用。
什么是滑动窗口?
滑动窗口技术通常用于解决子数组或子串相关的问题。其主要思想是在数组或字符串上维持一个固定的窗口大小,或在特定条件下调整窗口大小,从而在窗口内进行高效的计算。滑动窗口技术可以帮助我们在O(n)的时间复杂度内解决一些需要遍历整个数组或字符串的问题。
滑动窗口的基本步骤包括:
- 初始化窗口的左右边界(通常为两个指针)。
- 移动窗口的右边界扩展窗口范围,直至满足某些条件。
- 移动窗口的左边界收缩窗口,直至不再满足条件。
- 记录或更新需要的结果。
接下来,我们通过几道经典的滑动窗口问题,来深入理解这一技巧的应用。
经典题型分析与讲解
1. 长度最小的子数组
题目描述:
给定一个含有n个正整数的数组和一个正整数**target**
,找出该数组中满足其和大于等于**target**
的长度最小的连续子数组,并返回其长度。如果不存在符合条件的子数组,返回0。
滑动窗口思路:
- 我们使用两个指针
**left**
和**right**
表示窗口的左右边界。 - 初始时两个指针都指向数组的起点。
- 扩展
**right**
指针,使窗口内的数字和逐渐增大。 - 当窗口内的和大于等于
**target**
时,收缩**left**
指针以找到最小的子数组长度。 - 在整个过程中,动态更新最小长度。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0;int right = 0;int len = INT_MAX; // 初始化最小子数组长度为无穷大int n = nums.size();int sum = 0; // 当前窗口的数字和// 遍历数组,扩展右边界for (; right < n; right++) {sum += nums[right]; // 将当前右边界的数字加入窗口的和中// 当窗口内的和大于或等于目标值时,缩小窗口while (sum >= target) {len = min(len, right - left + 1); // 更新最小子数组长度sum -= nums[left]; // 减去左边界的数字,将窗口左边界右移left++;}}// 如果找不到符合条件的子数组,返回0;否则返回最小长度return len == INT_MAX ? 0 : len;}
};
复杂度分析:
- 时间复杂度:O(n),其中n为数组的长度。每个元素在扩展和收缩窗口的过程中最多只会被访问两次。
- 空间复杂度:O(1),仅使用了常数个额外空间。
2. 无重复字符的最长子串
题目描述:
给定一个字符串**s**
,请你找出其中不含有重复字符的最长子串的长度。
滑动窗口思路:
- 使用一个哈希表
**hash**
来记录窗口内字符的频率。 - 移动
**right**
指针扩展窗口,加入字符到哈希表中。 - 如果窗口内出现重复字符,则移动
**left**
指针收缩窗口,直到不再有重复字符。 - 在整个过程中,动态更新最大子串长度。
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[200] = { 0 }; // 用于记录字符的频率int left = 0;int right = 0;int 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;}
};
复杂度分析:
- 时间复杂度:O(n),字符串的每个字符最多访问两次。
- 空间复杂度:O(1),哈希表的大小为固定的常数级。
3. 最长重复子数组
题目描述:
给定一个二进制数组**nums**
和一个整数**k**
,如果可以将最多**k**
个**0**
变成**1**
,求最长的连续**1**
的长度。
滑动窗口思路:
- 使用两个指针
**left**
和**right**
表示滑动窗口。 - 每次扩展
**right**
指针,将遇到的**0**
记录在计数器**counter**
中。 - 当窗口内
**0**
的个数大于**k**
时,收缩窗口,直到**0**
的个数不超过**k**
。 - 在整个过程中,动态更新最大连续
**1**
的长度。
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0;int right = 0;int ret = 0;int counter = 0; // 记录窗口内0的个数for (; right < nums.size(); ++right) {if (nums[right] == 0) counter++; // 遇到0则计数器加1// 当窗口内0的个数超过k时,收缩窗口while (counter > k) {if (nums[left] == 0) counter--;left++;}// 更新最大长度ret = max(ret, right - left + 1);}return ret; // 返回最大长度}
};
复杂度分析:
- 时间复杂度:O(n),数组的每个元素最多访问两次。
- 空间复杂度:O(1),仅使用了常数个额外空间。
4. 将x减到0的最小操作数
题目描述:
给定一个整数数组**nums**
和一个整数**x**
,你可以从数组的开头或者末尾取元素来减小**x**
。请你返回最少需要多少次操作才能将**x**
减少到**0**
,如果无法实现,返回**-1**
。
滑动窗口思路:
- 计算数组总和
**sum**
,目标是找到一个和为**sum - x**
的最长子数组。 - 使用滑动窗口来找这个最长的子数组。
- 如果找到了目标子数组,则返回最少操作数,即
**nums.size() - 最大子数组长度**
。 - 否则返回
**-1**
。
class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = accumulate(nums.begin(), nums.end(), 0); // 计算数组总和int target = sum - x; // 目标是找和为 sum - x 的子数组if (target < 0) return -1; // 如果目标和为负数,直接返回-1if (target == 0) return nums.size(); // 如果目标和为0,返回整个数组长度int ret = 0, tmp = 0;for (int left = 0, right = 0; right < nums.size(); right++) {tmp += nums[right];// 当 tmp 大于目标值时,缩小窗口while (tmp > target) {tmp -= nums[left];left++;}// 找到一个和为 target 的子数组,更新 retif (tmp == target) ret = max(ret, right - left + 1);}// 返回最少操作数return ret == 0 ? -1 : nums.size() - ret;}
};
复杂度分析:
- 时间复杂度:O(n),数组的每个元素最多访问两次。
- 空间复杂度:O(1),仅使用了常数个额外空间。
5. 水果成篮 (LeetCode 904)
题目描述:
在一条树木组成的行上,有 n
棵树,每棵树上都挂着不同种类的水果。你只有两个篮子,每个篮子只能装一种类型的水果。你需要尽可能多地收集水果,但每次只能从连续的树上收集。
滑动窗口思路:
这道题可以看作是一个典型的滑动窗口问题,要求在一个数组中找到最多包含两个不同元素的最长子数组。我们通过滑动窗口来动态地调整当前子数组的左右边界,以找到满足条件的最长子数组。
代码分析:
class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> basket; // 用于记录每种水果的数量int max_fruits = 0; // 记录最多的水果数量int left = 0; // 窗口的左边界// 右边界从0开始移动for (int right = 0; right < fruits.size(); ++right) {basket[fruits[right]]++; // 将当前水果加入到篮子中// 如果篮子中的水果种类超过两种,调整左边界while (basket.size() > 2) {basket[fruits[left]]--; // 移除左边界的水果if (basket[fruits[left]] == 0) {basket.erase(fruits[left]); // 种类数量为0时移除该种类}left++; // 移动左边界}// 更新最大水果数量max_fruits = max(max_fruits, right - left + 1);}return max_fruits; // 返回结果}
};
详细解读:
- 初始化与边界控制:
basket
是一个哈希表,用于记录当前窗口中每种水果的数量。left
是窗口的左边界,right
是窗口的右边界。 - 窗口扩展:通过
right
指针逐渐扩展窗口,将当前水果加入到篮子中。 - 窗口收缩:如果篮子中的水果种类超过两种,开始通过
left
指针收缩窗口,直到篮子中只有两种或更少种类的水果。 - 结果更新:每次调整窗口后,计算当前窗口的长度,并更新
max_fruits
,以记录目前为止可以收集的最多水果数量。 - 返回结果:遍历整个数组后,
max_fruits
中记录的就是最多的连续水果数量。
6. 滑动窗口最大值 (LeetCode 239)
题目描述:
给定一个数组 nums
和滑动窗口大小 k
,请找出所有滑动窗口里的最大值。
滑动窗口 + 双端队列思路:
这道题的难点在于如何在每次滑动窗口移动时,快速找到当前窗口的最大值。我们可以借助一个双端队列 deque
来解决这个问题。deque
中保存的是元素在数组中的索引,并且这些索引对应的元素值在 deque
中是从大到小排列的。
代码分析:
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> dq; // 存储数组元素的索引vector<int> result;for (int i = 0; i < nums.size(); i++) {// 移除不在窗口范围内的元素if (!dq.empty() && dq.front() < i - k + 1) {dq.pop_front();}// 移除队列中比当前元素小的元素while (!dq.empty() && nums[dq.back()] <= nums[i]) {dq.pop_back();}dq.push_back(i); // 将当前元素的索引添加到队列// 当窗口大小达到 k 时,记录当前窗口的最大值if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;}
};
详细解读:
- 初始化队列与结果数组:
deque
用于存储数组元素的索引,result
存储最终的最大值。 - 维护双端队列:在遍历
nums
时,首先检查deque
的头部索引是否在当前窗口外,如果在则移除。然后,移除deque
中所有比当前元素小的元素,因为这些元素不可能成为当前窗口的最大值。 - 记录结果:当窗口的大小达到
k
时,deque
的头部元素就是当前窗口的最大值,将其添加到result
中。 - 返回结果:遍历完成后,返回
result
,其中存储了每个滑动窗口的最大值。
7. 字符串中的所有字母异位词 (LeetCode 剑指 Offer II 015)
题目描述:
给定一个字符串 s
和一个非空字符串 p
,找到 s
中所有是 p
的字母异位词的子串,返回这些子串的起始索引。
滑动窗口思路:
这道题与滑动窗口的使用密切相关,我们通过一个滑动窗口来逐步遍历字符串 s
,同时维护一个与字符串 p
的字符频率相匹配的哈希表,以此来判断当前窗口是否为 p
的字母异位词。
代码分析:
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret; // 存储结果的向量int hash1[26] = { 0 }; // 存储字符串 p 中字符的频率// 计算字符串 p 中每个字符的频率for (auto ch : p)hash1[ch - 'a']++;int hash2[26] = { 0 }; // 存储当前滑动窗口中字符的频率int left = 0, count = 0;for (int right = 0; right < s.size(); right++) {char in = s[right];hash2[in - 'a']++;if (hash2[in - 'a'] <= hash1[in - 'a'])count++;// 当窗口长度超过字符串 p 的长度时,调整窗口if (right - left + 1 > p.size()) {char out = s[left];if (hash2[out - 'a']-- <= hash1[out - 'a'])count--;left++;}// 如果 count 等于 p 的长度,说明找到一个字母异位词if (count == p.size())ret.push_back(left);}return ret;}
};
详细解读:
- 哈希表初始化:
hash1
存储字符串p
中每个字符的频率。 - 窗口扩展:
right
指针逐步扩展窗口,将当前字符添加到hash2
中,并检查是否符合p
的字符频率。 - 窗口收缩:当窗口大小超过
p
的长度时,调整left
指针,移除最左边的字符,并更新hash2
中的频率。 - 结果记录:如果当前窗口中符合
p
的所有字符频率,则记录当前窗口的起始位置。 - 返回结果:最终返回
ret
,其中存储了所有符合条件的起始索引。
8. 串联所有单词的子串 (LeetCode 30)
题目描述:
给定一个字符串 s
和一个字符串数组 words
,找出 s
中所有可以由 words
中所有单词串联形成的子串的起始位置。
滑动窗口思路:
这道题可以看作是将每个单词视为一个单位的滑动窗口问题,我们需要找到一个窗口,使得其中包含 words
中的所有单词,并且每个单词出现的次数都与 words
中的频率一致。
代码分析:
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1; // 保存 words 里面所有单词的频次// 统计 words 中每个单词的出现次数for (auto& word : words)hash1[word]++;int len = words[0].size(); // 单词的长度int m = words.size(); // 单词的数量// 执行 len 次(从不同的起点开始)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) {// 进窗口并维护 countstring in = s.substr(right, len);hash2[in]++;if (hash2[in] <= hash1[in]) count++;// 判断窗口大小是否超过了允许的大小,进行出窗口操作并维护 countif (right - left + len > len * m) {string out = s.substr(left, len);if (hash2[out] <= hash1[out]) count--;hash2[out]--;left += len;}// 更新结果,如果当前窗口内的单词数量和 words 中一致,记录左边界if (count == m) ret.push_back(left);}}return ret;}
};
详细解读:
- 哈希表初始化:
hash1
用于存储words
中每个单词的频率。 - 窗口扩展:
right
指针逐步扩展窗口,将当前单词添加到hash2
中,并检查是否符合words
中的频率。 - 窗口收缩:如果当前窗口大小超过了
words
中所有单词串联后的长度,则调整left
指针,移除最左边的单词,并更新hash2
。 - 结果记录:当
count
等于words
的长度时,说明当前窗口符合要求,将窗口的起始位置left
记录到ret
中。 - 返回结果:最终返回
ret
,其中存储了所有符合条件的起始索引。
9. 最小覆盖子串 (LeetCode 76)
题目描述:
给定一个字符串 s
和一个字符串 t
,找到 s
中包含 t
的所有字符的最小子串。
滑动窗口思路:
我们需要维护一个滑动窗口,使得窗口中的子串包含 t
的所有字符,且窗口尽可能小。
代码分析:
class Solution {
public:string minWindow(string s, string t){int hash1[128] = { 0 };int kinds = 0;// 初始化hash1,计算需要匹配的字符种类数kindsfor (auto a : t){if (hash1[a] == 0) kinds++;hash1[a]++;}int hash2[128] = { 0 };int begin = -1; // 用于记录最小子串的起始位置:int begin = -1; // 用于记录最小子串的起始位置int min_len = INT_MAX; // 记录最小子串长度for (int left = 0, right = 0, count = 0; right < s.size(); ++right){char in = s[right];hash2[in]++;// 如果当前字符频率与目标频率匹配,增加countif (hash2[in] == hash1[in]) count++;// 当所有字符频率都匹配时,开始尝试缩小窗口while (count == kinds){// 更新最小子串的起始位置和长度if (right - left + 1 < min_len){min_len = right - left + 1;begin = left;}char out = s[left];left++;// 移出左边界字符后,判断是否需要减少countif (hash2[out] == hash1[out]) count--;hash2[out]--;}}// 如果没有找到满足条件的子串,返回空字符串if (begin == -1) return "";return s.substr(begin, min_len);}
};
详细解读:
- 初始化哈希表:
hash1
用于记录字符串t
中每个字符的频率,并计算需要匹配的字符种类数kinds
。hash2
用于记录当前窗口中字符的频率。 - 窗口扩展:
right
指针逐步扩展窗口,将当前字符添加到hash2
中。如果当前字符在hash2
中的频率与hash1
中的频率相同,则增加count
。 - 窗口收缩:当
count
等于kinds
时,意味着当前窗口已经包含了t
中的所有字符,此时尝试缩小窗口。如果缩小后的窗口仍然包含t
中的所有字符,则更新最小子串的起始位置和长度。 - 判断结果:如果最终找到了符合条件的子串,返回该子串,否则返回空字符串。
总结
上述算法都使用了滑动窗口技术来解决问题。滑动窗口的核心思想是逐步扩展窗口,同时保持窗口的最优状态,尽可能减少不必要的计算。通过维护一个哈希表来记录窗口内的字符频率或单词频率,可以有效地判断当前窗口是否满足题目要求。每当窗口状态符合要求时,记录当前的结果,并尝试收缩窗口以找到更优解。