同向双指针滑动窗口算法：最大连续 1 的个数 III、将 x 减到 0 的最小操作数

011 最大连续 1 的个数 III

1.1 题目详解

1.2 算法原理以及代码实现

1.2.1 解法思路：滑动窗口

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

1.2.2 算法流程

初始化一些变量 left = 0，right = 0，ret = 0；
当 right 小于数组大小的时候，一直下列循环—— （1）让当前元素进入窗口，顺便统计到哈希表中；（2）检查 0 的个数是否超标：

1）如果超标，依次让左侧元素滑出窗口，顺便更新哈希表的值，直到 0 的个数恢复正常；（3）程序到这里，说明窗口内元素是符合要求的，更新结果；（4）right++，处理下一个元素；
循环结束后，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 的最小操作数

2.1 题目详解

2.2 算法原理

2.2.1 解法思路：滑动窗口

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

2.2.2 算法流程

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

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

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

同向双指针滑动窗口算法：最大连续 1 的个数 III、将 x 减到 0 的最小操作数

011 最大连续 1 的个数 III

1.1 题目详解

1.2 算法原理以及代码实现

1.2.1 解法思路：滑动窗口

1.2.2 算法流程

1.2.3 代码实现

1.3 博主手记

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

2.1 题目详解

2.2 算法原理

2.2.1 解法思路：滑动窗口

2.2.2 算法流程

2.2.3 代码实现

2.3 博主手记

更多推荐文章

相关免费在线工具

同向双指针滑动窗口算法：最大连续 1 的个数 III、将 x 减到 0 的最小操作数

011 最大连续 1 的个数 III

1.1 题目详解

1.2 算法原理以及代码实现

1.2.1 解法思路：滑动窗口

1.2.2 算法流程

1.2.3 代码实现

1.3 博主手记

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

2.1 题目详解

2.2 算法原理

2.2.1 解法思路：滑动窗口

2.2.2 算法流程

2.2.3 代码实现

2.3 博主手记

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具