如何统计子数组中1的个数？

Question

假设我有一个由 1 和 0 组成的数组，如下所示：

[1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1]

假设我有一个子数组，如下所示：

[1, 0, 0, 1]

如何在 O(1) 时间内找到给定子数组（如上面的子数组）中 1 的总数？

为实现上述情况而构造的方法应该花费 O(n) 时间。

我考虑过构造输入数组的前缀和（这应该需要 O(n) 时间）。

所以上面例子的前缀和数组是：

[1, 1, 1, 2, 3, 3, 4, 4, 4, 5, 6, 6, 7]

然后，当给定一个子数组时，我获取子数组的开始和结束索引 - 并将其与前缀和数组中的相应值相匹配，并减去如下值：

value at end index - value at start index

所以上面的示例子数组有

end index: 3

和

start index 0

如果查看前缀和数组中的索引

0

和

3

，我们分别得到值

1

和

2

。

所以按照公式我们做

 2 - 1

我们得到

1

。 所以这表明示例子数组中 1 的数量是 1，但实际上是 2。

所以这似乎不适用于包含输入数组的第一个或最后一个元素的子数组。非常感谢您的帮助。

Answer 1

“前缀和”数组很好并且应该可以工作。请注意，前缀和数组应比原始数组多一个元素。

如果原始数组

a

的索引从0到n-1，则前缀和数组

s

应该从0到n索引，其中

s[k]

等于前k个元素的总和：

s[0] = 0

和

s[k] = a[0] + ... + a[k-1] 

。那么子数组

start,end

之和等于

s[end+1]-s[start]

。

以你的例子：

a =    [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1]
s = [0, 1, 1, 1, 2, 3, 3, 4, 4, 4, 5, 6, 6, 7]

sum([1,0,0,1] = sum(start=0,end=3) = s[3+1] - s[0] = 2 - 0 = 2.

Answer 2

前缀和代码：

def create_prefix_sum_array(arr):
    prefix_sum = [0] * len(arr)
    prefix_sum[0] = arr[0]
    for i in range(1, len(arr)):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]
    return prefix_sum

def count_ones_in_subarray(prefix_sum, l, r):
    if l == 0:
        return prefix_sum[r]
    return prefix_sum[r] - prefix_sum[l - 1]