当所有值都非负时，我们真的可以避免额外的 space 吗？

Question

这个问题是我很久以前问过的问题的后续问题：

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.

在, @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

我认为这个算法可行，使用 O(1) space。

我们维护两个指向当前子序列开始和结束的指针，以及当前子序列的和。一开始，两个指针都指向array[0]，和显然设置为array[0].

将结束指针前移（从而将子序列向右扩展），并将总和增加它指向的值，直到总和超过k。然后前进起始指针（从而从左边收缩子序列），并减少总和，直到总和低于 k。继续这样做，直到结束指针到达数组的末尾。跟踪总和恰好为 k.

的次数

Answer 2

让我们从一个稍微简单的问题开始：所有值都是正数（没有零）。在这种情况下，子数组可以重叠，但不能相互包含。

即：arr = 2 1 5 1 1 5 1 2, Sum = 8

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

但这种情况永远不会发生：

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

考虑到这一点，有一种算法不需要额外的 space（好吧.. O(1) space）并且具有 O(n) 时间复杂度。思路是左右索引分别表示当前序列和当前序列的和

如果总和是 k 增加计数器，前进 left 和 right
如果总和小于k则提前right
否则提前left

现在，如果有零，区间可以相互包含，但前提是零位于区间的边缘。

适应non-negative个号码：

如上操作，除了：

前进时跳过零 left
如果总和为 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

当所有值都非负时，我们真的可以避免额外的 space 吗？

Can we really avoid extra space when all the values are non-negative?

c++

algorithm

memory

space-complexity