引言
在算法学习过程中，滑动窗口是一种非常实用且高频出现的解题技巧。它能够高效地处理数组、字符串等序列数据，在很多求子数组、子字符串相关问题中大放异彩。今天就来分享三道运用滑动窗口解决的中等难度算法题，以及对应的代码实现和解题思路。
一、1004. 最大连续1的个数 III
题目描述
给定一个二进制数组 nums 和一个整数 k ，假设最多可以翻转 k 个 0 ，返回执行操作后数组中连续 1 的最大个数。
解题思路
利用滑动窗口，维护一个窗口内最多有 k 个 0 。
- 初始化左右指针 left 、 right 都为 0 ，以及记录窗口内 0 的个数 zero 为 0 。
- 右指针 right 不断右移，每遇到一个 0 ， zero 加 1 。
- 当 zero 超过 k 时，说明窗口内 0 的个数过多，需要移动左指针 left ，若移动的 nums[left] 是 0 ，则 zero 减 1 。
- 每次移动指针后，更新连续 1 的最大长度，即 ret = max(ret, right - left + 1) 。
代码实现（C++）
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int ret;
for(int left=0,right=0,zero=0;right<nums.size();right++)
{
if(nums[right]==0)zero++;
while(zero>k)if(nums[left++]==0)zero--;
ret=max(ret,right-left+1);
}
return ret;
}
};
二、3. 无重复字符的最长子串
题目描述
给定一个字符串 s ，找出其中不含有重复字符的最长子串的长度。
解题思路
使用滑动窗口和哈希表。
- 初始化左右指针 left 、 right 为 0 ，用一个大小为 128 的数组 hash 记录字符出现的次数（因为字符的 ASCII 码范围相关）， n 为字符串长度， temp 记录最长子串长度。
- 右指针 right 右移，将 s[right] 字符出现次数加 1 。
- 若 s[right] 字符出现次数大于 1 ，说明窗口内有重复字符，移动左指针 left ，并将 s[left] 字符出现次数减 1 。
- 每次移动指针后，更新最长子串长度 temp = max(temp, right - left + 1) 。
代码实现（C++）
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int left=0,right=0;
int hash[128]={0};
int n=s.size(),temp=0;
while(right<n)
{
hash[s[right]]++;
while(hash[s[right]]>1)
hash[s[left++]]--;
temp=max(temp,right-left+1);
right++;
}
return temp;
}
};
三、1658. 将 x 减到 0 的最小操作数
题目描述
给一个整数数组 nums 和一个整数 x 。每一次操作时，应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。如果可以将 x 恰好减到 0 ，返回最小操作数；否则，返回 -1 。
解题思路
本题关键在于转化为求数组中和为 sum(nums) - x 的最长子数组。
- 先遍历数组 nums 求和 add ，计算目标值 target = add - x 。若 target < 0 直接返回 -1；若 target == 0 直接返回数组长度。
- 初始化左右指针 left 、 right 为 0 ，以及窗口内元素和 sum 为 0 ， ret 记录最长子数组长度。
- 右指针 right 右移，将 nums[right] 加入 sum 。
- 当 sum > target 时，移动左指针 left ，并将 nums[left] 从 sum 中减去。
- 若 sum == target ，更新最长子数组长度 ret = max(ret, right - left + 1) 。
- 最后根据 ret 的值判断返回结果，若 ret == -1 说明不存在满足条件的子数组，返回 -1；否则返回数组长度减去 ret 。
代码实现（C++）
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int add=0;
for(auto e:nums)add+=e;
int target=add-x;
if(target<0)return -1;
//if(target==0)return nums.size();
int ret=-1;
for(int left=0,right=0,sum=0;right<nums.size();right++)
{
sum+=nums[right];
while(sum>target)
sum-=nums[left++];
if(sum==target)
ret=max(ret,right-left+1);
}
if(ret==-1)return -1;
else return nums.size()-ret;
}
};
总结
滑动窗口通过动态调整窗口的左右边界，能够在一次遍历中高效解决很多关于子数组、子字符串的问题。在实际解题时，关键是要明确窗口内维护的条件，以及如何根据条件移动窗口边界。希望通过这三道题目的分享，能帮助大家更好地掌握滑动窗口这一重要的算法技巧。后续还会继续分享更多算法题目的解题思路，欢迎一起交流学习！