【优选算法必刷100题】第011~012题（滑动窗口）：最大连续1的个数 III，将 x 减到 0 的最小操作数

用户11915063

发布于 2025-11-20 13:06:17

011.最大连续1的个数

题目链接：

1004. 最大连续1的个数 III - 力扣（LeetCode）

题目描述：

题目示例：

解法 (滑动窗口)：

算法思路：

千万不想把问题想复杂了，数组无非不是1就是0，
我们要做的就是在数组的子数组中寻找0的个数zero<k的最长的那一个子数组
既然是连续区间，且定义两个指针的话，都是向同一个方向走，可以考虑使用【滑动窗口】来解决问题

算法流程：

定义两个下标left=0，right=0，计数器（统计子区间内0的个数）zero=0，ret=0；
当right<nums.size()就一直进行下面的循环操作

当前元素（numsp[right]）进入窗口

进行判断，如果这个数是1就无视，如果是0就让计数器zero++

判断zero>k，如果成立，就让nums[left]滑出窗口，并让计数器zero--，直到zero合法为止

程序到这里，说明窗口内元素是符合要求的，更新结果

循环结束后， ret 存的就是最终结果

C++代码演示：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int zero=0,n=nums.size(),ret=0;
        for(int left=0,right=0;right<n;right++)
        {
            if(nums[right]==0) zero++;
            while(zero>k)
                if(nums[left++]==0) zero--; 
            ret=max(ret,right-left+1);
        }    
        return ret;
    }
};

算法总结&&笔记展示：

博主笔记（字迹有点丑，请大家见谅）：

012.将x减到0的最小操作数

题目链接：

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

题目描述：

题目示例：

解法 (滑动窗口)：

算法思路：

题目要求在数组的左端或者右端进行删除数据，此时就隐含了左右两端是连续的区间，所以中间也就是连续的区间，连续的区间就可以联想到用滑动窗口来解决

算法流程：

转化：要求进行最少次数的减为0的操作数，此时就可以转化为找子数组，是的子数组最长并且子数组之和为target（sum-x）
初始化两个指针，left=0，right=0，[left，right）区间的和tmp=0
right<nums.size()就进入循环

首先进窗口，并计算tmp的值，tmp+=nums[right]

然后进行判断，tmp>target，成立就让左指针滑出窗口，区间和减去做指针的值

当tmp==target，说明此时找到连续的区间并且区间和为sum-x,更新结果

当遍历结束，判断是否找到了连续的区间并且区间和为sum-x，若没有找到，就返回-1，找到了就返回nums.size()-ret

C++代码演示：

class Solution {
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int sum=0;
        for(int i:nums) sum+=i;
        int target=sum-x;
        if(target<0) return -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) return ret;
        else return nums.size()-ret;
    }
};