当前位置：首页 > news >正文

算法刷题记录：滑动窗口经典题目解析

news 2025/5/31 12:00:40

引言

在算法学习过程中，滑动窗口是一种非常实用且高频出现的解题技巧。它能够高效地处理数组、字符串等序列数据，在很多求子数组、子字符串相关问题中大放异彩。今天就来分享三道运用滑动窗口解决的中等难度算法题，以及对应的代码实现和解题思路。

一、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;}
};