在仅包含 0 和 1 的数组 a 中，k 位翻转涉及选择长度为 k 的（连续）子数组，同时将子数组中的每个 0 更改为 1，将每个 1 更改为 0。
返回所需的最小 k 位翻转次数，以便数组中没有值为 0 的元素。 如果无法做到这一点，请返回 -1。
示例 1：输入：a = [0,1,0]， k = 1
输出：2 解释：先翻转 a[0]，然后翻转 a[2]。
示例 2：输入：a = [1,1,0]， k = 2
输出：-1 解释：无论我们如何翻转大小为 2 的子数组，我们都无法制作数组 [1,1,1]。
示例 3：输入：a = [0,0,0,1,0,1,1,0]， k = 3
输出： 3 解释：
翻转 a[0]，a[1]，a[2]：a 变为 [1,1,1,1,0,1,1,0]。
翻转 a[4]，a[5]，a[6]：a 变为 [1,1,1,1,1,1,1,0,0,0]。
翻转 a[5]，a[6]，a[7]：a 变为 [1,1,1,1,1,1,1,1,1]。
提示：
1 <= a.length <= 30000连续子阵列优化首先考虑暴力破解。 蛮力的想法可以从左到右遍历数组，如果我们击中零，我们将其向左翻转。 翻转的长度自然是一个子数组，其起始长度为 k。 原样用它作为左端翻转它，所以如果我们遇到一个 0，我们必须执行翻转，否则我们无法获得完整的 1 数组。 由于翻转的顺序不会影响最终结果，即如果最终答案是翻转以 i、j、k 开头的子数组，那么谁先翻转然后翻转，谁就是一样的。 因此，可以从左到右遍历。1 <= k <= a.length
总结一下：蛮力的思路可以是从左到右遍历数组，如果我们打到一个0，我们把它翻转到左边，在当前位置的开头修改长度为k的子数组，同时计数器+1，如果数组不全是0，最后返回-1， 否则返回计数器的值。
语言支持：python3python3 代码：
class solution: def minkbitflips(self, a, k): n = len(a) ans = 0 for i in range(n - k + 1): if a[i] == 1: continue for j in range(k): a[i + j] ^= 1 ans += 1 for i in range(n): if a[i] == 0: return -1 return ans设 n 为数组的长度。
时间复杂度：$o（n * k）$Space复杂度：$o（1）$For这种连续子阵列的问题。 一般来说，只有几个优化思路。 让我们列举一下：
前缀和 & 差异分数组滑动窗口双端队列。 例如，1696跳跃游戏 vi 和 239Sliding Window Max 是一种思维方式。 我已经写过这三种技术，所以如果你不了解它们，你可以先看看它们。
对于这个问题，我们可以使用差异组或双端队列进行优化。 无论采用哪一种，基本思想都是相似的，也可以对比下面的**，看看他们思想的一致性。 简单来说，他们的思维是相似的，区别只是用于解决问题的数据结构不同，因此API不同。 因此，我不认为这两者是两种解决方案。
对于差分组，在上述蛮力解的内层中有一个 k 的循环。 另一方面，如果仅使用差分组修改端点的值，则可以轻松地将时间复杂度优化为 $o（n）$。
对于双端队列，如果需要翻转当前位置，则将其排队。 那么，你怎么知道你当前位置的数字是多少呢？ （可能是由于前一位数字的翻转，当前位置。是翻了几次，可能不是以前的数字）。由于偶数次翻转等于不翻转，奇数次翻转效果相同，因此只需要记录翻转的奇偶校验。 这实际上是队列长度的奇偶校验。 因为队列的长度是当前号码被翻转的次数。当然，这需要您从队列中删除那些已经超过 k 的。
连续子阵列优化技巧 语言支持： python3python3 代码：
差异分数组：
class solution: def minkbitflips(self, a: list[int], k: int) -int: n = len(a) diff = [0] *n + 1) ans, cur = 0, 0 for i in range(n): cur += diff[i] if cur % 2 == a[i]: if i + k > n: return -1 ans += 1 cur += 1 diff[i + k] -= 1 return ans设 n 为数组的长度。
时间复杂度：$o（n）$Spatial复杂度：$o（n）$double结束队列：
class solution: def minkbitflips(self, a, k): n = len(a) q = collections.deque() ans = 0 for i in range(n): if q and i >= q[0] +k: q.popleft() if len(q) %2 == a[i]: if i + k > n: return -1 q.append(i) ans += 1 return ans设 n 为数组的长度。
时间复杂度：$o（n）$Spatial复杂度：$o（k）$Regardless 不管是使用差分组还是双端队列，都不需要使用额外的数据结构，而是使用原来的数组 a，即原位修改
例如，我们只能记录双端队列的长度，并且要确定队列中是否有一个数字，我们只需要将其映射到问题数据范围内的另一个数字即可。 由于问题数据范围为 [0,1]，我们可以将其映射到 2。
原位修改语言支持：python3python3 代码：
class solution: def minkbitflips(self, a, k): flips = ans = 0 for i in range(len(a)):if i >= k and a[i - k] -2 == 0: flips -= 1 if (flips % 2) == a[i]: if i + k > len(a): return -1 a[i] = 2 flips += 1 ans += 1 return ans设 n 为数组的长度。
时间复杂度：$o（n）$Space复杂度：$o（1）$