如何检查连续子数组的总和是否等于N？

Question

如何检查连续子数组的总和是否等于N？

3

假设我有这样一个序列列表。

我想要移除所有总和等于N的序列和/或包含连续子数组和为N的序列。

例如，如果N = 4，则(1,1,2)无效，因为它们的总和是4。(1,1,3)也不合法，因为(1,3)的和也是4。(1,3,1)由于相同的原因也无效。

lst = [ 
    (1,1,1), (1,1,2), (1,1,3), 
    (1,2,1), (1,2,2), (1,2,3), 
    (1,3,1), (1,3,2), (1,3,3), 
    (2,1,1), (2,1,2), (2,1,3), 
    (2,2,1), (2,2,2), (2,2,3), 
    (2,3,1), (2,3,2), (2,3,3), 
    (3,1,1), (3,1,2), (3,1,3), 
    (3,2,1), (3,2,2), (3,2,3), 
    (3,3,1), (3,3,2), (3,3,3) 
]

有什么方法可以做到这一点吗？

我目前正在尝试查看是否能够删除总和不一定是N的倍数但不删除其连续子数组的序列，但我一直没有成功。

   for elements in list(product(range(1,n), repeat=n-1)):
        lst.append(elements)
    for val in lst:
        if np.cumsum(val).any() %n != 0:
            lst2.append(val) # append value to a filtered list

- Thegreatfoo

你的小序列（如1,1,3）中的数字是否保证非负？此外，这些“小”序列的最大长度是多少？ - eozd

是的，它们保证为负数且最大长度为N-1。 - Thegreatfoo

你的意思是它们保证是非负数吗？如果是这样，Neb提供了一个非常高效的线性时间解决方案。@Thegreatfoo 所以，我认为在问题中也值得提及N可以有多大，元素的负性条件是什么。 - eozd

非负数，我的错误。此外，在这种情况下，N的范围为2 <= n <= 1000。 - Thegreatfoo

2个回答

2

你可以使用 itertools.combinations 来生成所有的切片索引组合，以测试子序列的和：

from itertools import combinations
[t for t in lst if not any(sum(t[l:h+1]) == 4 for l, h in combinations(range(len(t)), 2))]

这将返回：

[(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 1), (3, 2, 3), (3, 3, 2), (3, 3, 3)]

- blhsing

如果最大长度为N-1，则操作员可能需要将其推广到任何N。 - Cohan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Neb · Accepted Answer

您可以将问题分成两个子问题：

The elements in your list sum up to N. Then you can simply test:
```
if sum(myList) == N:
    # do fancy stuff
```
The elements in your list do not sum up to N. In this case, there might be a subsequence that sum up to N. To find it, let's define two pointers, l and r. Their name stand for left and right and will define the boundaries of your subsequence. Then, the solution is the following:
```
r = 1
l = 0
while r <= len(myList):
    sum_ = sum(myList[l:r])
    if sum_ < 4:
        r += 1
    elif sum_ > 4:
        l += 1
    else:
        # do fancy stuff and exit from the loop
        break
```
It works as follows. First you initialize l and r so that you consider the subsequence consisting of only the first element of myList. Then, you sum the element of the subsequence and if the sum is lower than N, you enlarge the subsequence by adding 1 to r. If it is greater than N, then you restrict the subsequence by adding 1 to l.

注：感谢 eozd:

上述算法仅适用于列表中元素为非负数的情况。