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

艾莉丝努力练剑

发布于 2025-11-18 13:19:45

200

文章被收录于专栏：C / C++C / C++

011 最大连续1的个数 III

力扣链接：1004. 最大连续1的个数 III

力扣题解链接：滑动窗口解决【最大连续1的个数III】问题

题目描述：

1.1 题目详解

1.2 算法原理以及代码实现

1.2.1 解法思路：滑动窗口

不要去想怎么翻转，不要把问题想的很复杂，这道题的结果无非就是一段连续的1中间塞了k个0。因此，我们可以把问题转化成：求数组中一段最长的连续区间，要求这段区间内的个数不超过k个。既然是连续区间，可以考虑使用「滑动窗口」来解决问题。

1.2.2 算法流程

1、初始化一个大小为2的数组就可以当做哈希表（hash）了；初始化一些变量left = 0，right =0，ret = 0；

2、当right小于数组大小的时候，一直下列循环——

（1）让当前元素进入窗口，顺便统计到哈希表中；

（2）检查 0 的个数是否超标：

1）如果超标，依次让左侧元素滑出窗口，顺便更新哈希表的值，直到的个数恢复正常；

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

（4）right++，处理下一个元素；

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

1.2.3 代码实现

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        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;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)。

1.3 博主手记

本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己推导很重要！

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

力扣链接：1658. 将 x 减到 0 的最小操作数

力扣题解链接：滑动窗口解决【将 x 减到 0 的最小操作数】问题

题目描述：

2.1 题目详解

2.2 算法原理

2.2.1 解法思路：滑动窗口

题目要求的是数组「左端+右端」两段连续的、和为x的最短数组，信息量稍微多一些，不易理清思路；我们可以转化成求数组内一段连续的、和为sum(nums) - x的最长数组。此时，就是熟悉的「滑动窗口」问题了。

这道题和我们介绍【滑动窗口】的第一道题目LCR 008. 长度最小的子数组有点像。

2.2.2 算法流程

1、转化问题：求target = sum(nums) - x。如果target＜0，问题无解; 2、初始化左右指针 l = 0，r = 0（滑动窗口区间表示为 [ l，r) ，左右区间是否开闭很重要，必须设定与代码一致），记录当前滑动窗口内数组和的变量sum=◎，记录当前满足条件数组的最大区间长度maxLen = -1； 3、当小于等于数组长度时，一直循环：

（1）如果sum<target，右移右指针，直至变量和大于等于target，或右指针已经移到头；（2）如果sum>target，右移左指针，直至变量和小于等于target，或左指针已经移到头；（3）如果经过前两步的左右移动使得sum == target，维护满足条件数组的最大长度，并让下个元素进入窗口。

4、循环结束后，如果maxLen的值有意义，则计算结果返回；否则，返回 -1。

2.2.3 代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int a : nums)sum += a;
        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：和sum区分
        {
            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;
    }
};