最大连续1的个数III.md

最大连续1的个数 III

题目描述

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回数组中连续 1 的最大个数 。

示例 1： 输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。

解题思路

本题有解题思路，且一次编程就通过，虽然提前知道了是滑动窗口的题目，但却是头一回这么顺利

• 本体可以转换为，找一个最长子数组，其中最多包含 k 个 0。
• 确定是滑动窗口之后就要进行滑动窗口三要素，左右窗口初始化在哪，左右窗口如何移动以及答案如何更新。
• 左右窗口初始化：左窗口初始化为 0，右窗口初始化为 0，最极端情况下k为0，且数组中全部值为0，所以答案也初始化为0。
• 需要一个变量count来记录窗口中0的个数，当count大于k时，左窗口右移，直到左窗口中移出一个0，这个时候将count的值重置为k。

    if nums[right] == 0:
        count += 1
    while count > k:
        if nums[left] == 0:
            count -= 1
        left += 1

• 这里重点说一下如何优化代码。上述代码段是逻辑的直观编译，但在涉及到count数值变动的时候均可以缩减成一行代码,如下所示。

    for right, x in enumerate(nums):
        count += 1 - x
        while count > k:
            count -= 1- nums[left]
            left += 1

• 本质上就是把if的判断条件移动到表达式里面。