整型列表的MovingSum

Question

我想计算一个窗口大小为3的整数列表的移动和。我有一个这样的类:

class MovingSum:
def __init__(self, window=3):
self.window = window

def push(self, nums: List[int]):
pass
def belongs(self, total) -> bool:
pass

我需要计算3个数字的移动和，并跟踪总数。例子:Movingsum。Push([1,2,3,4])将计算(1,2,3)和4的和，因此它保留两个总数，即6和4。然后接下来调用Movingsum.push([10])将更新总数，因此我们得到以下总数:6和14。然后Movingsum.push([20])将更新总数，因此我们有6和34。现在，下一个电话给动和。因此，Push([10,20,30])将计算出3个总数:6,34和60等。因此，我需要跟踪运行总数。我在更新我已经计算过的总数时遇到了问题。

我的尝试:

def __init__(self, window=3):
self.window = window
self.totals = set()
self.count = 0
def push(self, nums: List[int]):
total = 0
for num in nums:
total += num
self.count += 1
if self.count % 3 == 0:
self.totals.add(total)
self.count = 0
def belongs(self, total) -> bool:
return total in self.totals

中所属函数需要检查总数是否已经计算过。我不知道如何更新新的总数。由于

移动和需要在移动到下一个3等之前计算3个数字测试用例:开始:

nums = [1, 2]
MovingSum.push(nums)
Now total is 3
MovingSum.push([10, 20])

现在总数是13和20(因为在第一次推送时，我们计算了两个值为3的数字的总数，但我们需要总共3个数字。因此，将total更新为3 + 10(其中有3个数字)，并且由于只剩下一个数字，我们有两个总数:13和20

MovingSum.push([40])

更新total: 13,60(因为total of 20只有一个数字)

MovingSum.push([100, 20, 30])

更新总数:13,160,50(第三个总数是20 + 30，这是两个数字)

MovingSum.push([40, 100])

更新总数:13,160,90,100(因为90是20 + 30 + 40的和)，我们剩下一个数字是100。

Answer 1

如果我理解正确的话，您有一个恒定的数字流，并且您想要其中每个n项窗口(我称之为组)的总数。因此，您需要一个包含到目前为止所有组的总数的列表，并且您需要跟踪当前(部分)组中项目的运行总数，以及部分组中的项目数量。

下面的代码实现了这一点——我相信使用itertools之类的特性会更清晰，但我尽量保持简单，这样你就可以看到发生了什么。

class MovingSum:
window_size: int
totals: list[int]
count: int
def __init__(self, window_size: int = 3):
self.window_size = window_size
self.totals = []
self.count = 0
def push(self, nums: list[int]) -> None:
offset = 0
# Handle partial set as a special case, since the final total
# needs incrementing rather than a new total being added.
if self.count > 0:
items = nums[:self.window_size - self.count]
offset = len(items)
self.totals[-1] += sum(items)
self.count = (self.count + offset) % self.window_size
# Iterate over the remaining items, and stop once we run out.
# Whilst we have full groups, self.count will remain 0, but
# the final group may be partial so we recalculate it each loop.
while offset < len(nums):
items = nums[offset:offset + self.window_size]
self.totals.append(sum(items))
self.count = len(items) % self.window_size
offset += self.window_size
def belongs(self, total: int) -> bool:
if self.count > 0:
return total in self.totals[:-1]
else:
return total in self.totals

上面的belongs()函数也从成员检查中排除了部分总数，但是如果您不需要这种额外的复杂性，您的简单版本将工作得很好。

作为题外话，当totals变大时，belongs()函数将变得相当慢。对于几百个条目，这不会是一个问题，但如果你有上万个或更多的条目，set()是一种更有效的检查成员的方式——它还可以相当方便地处理重复数据删除。