优选算法——滑动窗口2
优选算法——滑动窗口
1.1004. 最大连续1的个数 III
题目描述
思路分析
这道题的核心是：找一个最长的子数组，其中最多包含 k 个 0。
经典的 滑动窗口 问题。
为什么用滑动窗口？
- 我们需要连续区间 → 滑动窗口天然适合
- 窗口内维护「0 的个数 ≤ k」这个约束
- 窗口扩张：右指针右移，遇到 0 就计数
- 窗口收缩：当 0 的个数超过 k，左指针右移直到满足条件
算法流程
1. 初始化：left = 0, zeroCount = 0, maxLen = 0 2. 遍历数组，right 指针右移： - 如果 nums[right] == 0，zeroCount++ - 当 zeroCount > k 时，收缩左边界： - 如果 nums[left] == 0，zeroCount-- - left++ - 更新 maxLen = max(maxLen, right - left + 1) 3. 返回 maxLen 
代码实现
classSolution{public:intlongestOnes(vector<int>& nums,int k){int zero=0;int ret=0;for(int left=0,right=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;}};2.1658. 将 x 减到 0 的最小操作数
题目描述
给定一个整数数组 nums 和整数 x。每次操作可以从数组最左端或最右端移除一个元素，使 x 减去该元素的值。返回将 x 恰好减到 0 的最小操作数，无法实现则返回 -1。
示例：
输入：nums = [1,1,4,2,3], x = 5 输出：2 解释：移除最右端的 3，再移除最右端的 2，x = 5 - 3 - 2 = 0 思路分析
逆向思维 + 滑动窗口
从两端取数 → 等价于找一个中间连续子数组，其和为 total - x。
- 设数组总和为
sum - 问题转化为：找最长的子数组，使其和为
sum - x - 最小操作数 =
n - 最长子数组长度
为什么？
- 两端取走的元素和 =
x - 剩下中间的元素和 =
sum - x - 操作数最少 → 中间剩余最长
算法流程
1. 计算 target = sum(nums) - x 2. 如果 target < 0，返回 -1（总和都不够减） 3. 滑动窗口找和为 target 的最长子数组 4. 返回 n - maxLen（若 maxLen 有效） 
代码实现
classSolution{public:intminOperations(vector<int>& nums,int x){int sum =0;int cmp=0;int ret=-1;for(auto e :nums){ sum+=e;}int target=sum-x;if(target<0)return-1;for(int left=0,right=0;right<nums.size();right++){ cmp+=nums[right];//进窗口while(cmp>target)//判断{ cmp-=nums[left++];//出窗口}if(cmp==target)//更新结果 ret=max(ret,right-left+1);}if(ret==-1)return ret;elsereturn nums.size()-ret;}};
