c++ - 当所有值均为非负数时，我们真的可以避免多余的空间吗？

Question

这个问题是我很久以前问过的another one的后续版本:

We have been given an array of integers and another number k and we need to find the total number of continuous subarrays whose sum equals to k. For e.g., for the input: [1,1,1] and k=2, the expected output is 2.

在 accepted answer中， @talex说:

PS: BTW if all values are non-negative there is better algorithm. it doesn't require extra memory.

尽管那时我并没有考虑太多，但现在我对此感到很好奇。恕我直言，我们将需要额外的内存。如果所有输入值均为非负数，我们的运行(前缀)总和将继续增加，因此，可以肯定的是，我们不需要 unordered_map来存储特定总和的频率。但是，我们仍然需要额外的内存(也许是 unordered_set)来存储我们沿途运行的(前缀)总和。这显然与 @talex所说的相矛盾。
有人可以确认我们是否绝对需要额外的内存，还是可以避免？
谢谢!

Answer 1

让我们从一个稍微简单的问题开始:所有值都是正数(无零)。在这种情况下，子阵列可以重叠，但不能包含彼此。
即:arr = 2 1 5 1 1 5 1 2，Sum = 8

2 1 5 1 1 5 1 2
|---|
  |-----|
      |-----|
          |---|

但是这种情况永远不会发生:

* * * * * * *
  |-------|
    |---|

考虑到这一点，有一种算法不需要额外的空间(好.. O(1)空间)，并且具有 O(n)时间复杂度。想法将具有指示当前序列和当前序列之和的左右索引。

如果总和为k，则增加计数器，前进left和right

如果总和小于k，则提前right

else前进left

现在，如果零为零，则间隔可以包含另一个，但前提是零位于间隔的边界。
要适应非负数:
执行上述操作，除了:

推进left

时跳过零

如果sum为k:

计数right右边连续的零，说zeroes_right_count

计数left左侧的连续零。可以说zeroes_left_count

而不是像以前那样增加计数，而是通过以下方式增加计数器:(zeroes_left_count + 1) * (zeroes_right_count + 1)

例:

... 7 0 0 5  1  2 0 0 0 9 ...
          ^     ^
          left  right         

这里我们在左边有2个零，在右边有3个零。这使得 (2 + 1) * (3 + 1) = 12序列的总和为 8:

5 1 2
5 1 2 0
5 1 2 0 0 
5 1 2 0 0 0

0 5 1 2 
0 5 1 2 0
0 5 1 2 0 0 
0 5 1 2 0 0 0

0 0 5 1 2
0 0 5 1 2 0
0 0 5 1 2 0 0 
0 0 5 1 2 0 0 0