arrays - 算法:找到包含 K 个 0's in array of 1' 和 0 的最小连续数组

Question

我只有 1 和 0 的数组。现在我想找到至少包含 K 个 0 的最小连续子集/子数组。

例子 数组是 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 K(6) 应该是 0 0 1 0 1 1 0 0 0 或 0 0 0 0 1 0 1 1 0....

我的解决方案

     Array: 1 1 0 1 1 0 1 1 0  0  0  0  1  0  1  1  0  0  0   1  1  0  0
     Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  20 21 22 23
     Sum:   1 2 2 3 4 4 5 6 6  6  6  6  7  7  8  9  9  9  9  10 11 11 11
Diff(I-S):  0 0 1 1 1 2 2 2 3  4  5  6  6  7  7  7  8  9 10  10 10 11 12

对于 K(6)

从 9-15 开始 = 在 diff 中存储差异。

下一步增加差异 8-15(指数差异) 8-14(指标差异比较)

继续寻找元素最少的元素...

我正在为这个解决方案寻找更好的算法。

Answer 1

我相信你可以用像这样的滚动窗口来做到这一点:

1. 在给定的数组中，找到第一次出现的 0(比如在索引 i 处)。
2. 继续扫描，直到您找到 k 0 包含在您的窗口中(例如，窗口以索引 j 结束)记录窗口长度(例如 j-i+1=L)。
3. 现在，丢弃索引 i 处最左边的 0 , 并继续扫描直到你得到下一个 0 (比如索引 i'
4. 扩展位于 j 的窗口的右端至 j'使 0 的计数 = k再次。
5. 如果新窗口长度L'=j'-i'+1小了就更新吧。
   
   

继续重复上述过程直到j到达数组的末尾。

不需要额外的空间，它是 O(N)时间复杂度，因为一个元素最多会被扫描两次。