当所有值均为非负数时，我们真的可以避免多余的空间吗? [英] Can we really avoid extra space when all the values are non-negative?

问题描述

这个问题是另一个问题的跟进，我已经问了很久:

This question is a follow-up of another one I had asked quite a while ago:

我们得到了一个整数数组和另一个数字k，我们需要找到总和等于k的连续子数组的总数.例如，对于输入: [1,1,1] 和 k = 2 ，预期输出为 2 .

在接受的答案中，

PS:顺便说一句，如果所有值都不为负，则有更好的算法.它不需要额外的内存.

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

虽然我当时对此并没有考虑太多，但现在我对此感到很好奇.恕我直言，我们将需要额外的内存.如果所有输入值均为非负数，我们的运行(前缀)总和将继续增加，因此，可以肯定的是，我们不需要 unordered_map 来存储特殊金额.但是，我们仍然需要额外的内存(也许是 unordered_set )来存储我们沿途获得的运行(前缀)总和.这显然与 @talex 所说的相矛盾.

While I didn't think much about it then, I am curious about it now. IMHO, we will require extra memory. In the event that all the input values are non-negative, our running (prefix) sum will go on increasing, and as such, sure, we don't need an unordered_map to store the frequency of a particular sum. But, we will still need extra memory (perhaps an unordered_set) to store the running (prefix) sums that we get along the way. This obviously contradicts what @talex said.

有人可以确认我们是否绝对需要额外的内存，还是可以避免?

Could someone please confirm if we absolutely do need extra memory or if it could be avoided?

谢谢！

推荐答案

让我们从一个稍微简单的问题开始:所有值均为正(无零).在这种情况下，子数组可以重叠，但不能包含彼此.

Let's start with a slightly simpler problem: all values are positive (no zeros). In this case the sub arrays can overlap, but they cannot contain one another.

即:arr = 2 1 5 1 1 5 1 2 ，总和= 8

I.e.: arr = 2 1 5 1 1 5 1 2, Sum = 8

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

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

But this situation can never occur:

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

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

With this in mind there is algorithm that doesn't require extra space (well.. O(1) space) and has O(n) time complexity. The ideea is to have left and right indexes indicating the current sequence and the sum of the current sequence.

• 如果总和为 k ，则递增计数器，将 left 和 right
前进
• 如果总和小于 k ，则前进 right
• 其他左

• if the sum is k increment the counter, advance left and right
• if the sum is less than k then advance right
• else advance left

现在，如果零为零，则间隔可以包含另一个，但前提是零位于间隔的边缘.

Now if there are zeros the intervals can contain one another, but only if the zeros are on the margins of the interval.

要适应非负数:

执行上述操作，除了:

• 向左前进向左
时跳过零
• 如果总和为 k :
  在 right 的右边
  • 计算连续的零，可以说 zeroes_right_count
  • 计数 left 左侧的连续零.可以说 zeroes_left_count
  • 不是像以前那样增加计数，而是将计数器增加:(zeroes_left_count + 1)*(zeroes_right_count + 1)
  • skip zeros when advancing left
  • if sum is k:
    • count consecutive zeros to the right of right, lets say zeroes_right_count
    • count consecutive zeros to the left of left. lets say zeroes_left_count
    • instead of incrementing the count as before, increase the counter by: (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 ，

    Here we have 2 zeroes to the left and 3 zeros to the right. This makes (2 + 1) * (3 + 1) = 12 sequences with sum 8 here:

    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
    

    这篇关于当所有值均为非负数时，我们真的可以避免多余的空间吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！