不同的连续子阵列的数量

Question

import math
n=7 #length of list
k=2 #number
arr=[1,1,1,1,4,5,1]
l=n

def segmentedtree(segmentedtreearr,arr,low,high,pos):  #function to build segment tree
    if low==high:
        segmentedtreearr[pos]=arr[high]
        return
    mid=(low+high)//2
    segmentedtree(segmentedtreearr,arr,low,mid,((2*pos)+1))
    segmentedtree(segmentedtreearr,arr,mid+1,high,((2*pos)+2))
    segmentedtreearr[pos]=segmentedtreearr[((2*pos)+1)]+segmentedtreearr[((2*pos)+2)]

flag=int(math.ceil(math.log2(n))) #calculating height of segment tree
size=2*int(math.pow(2,flag))-1#calculating size

segmentedtreearr=[0]*(size)


low=0
high=l-1
pos=0
segmentedtree(segmentedtreearr,arr,low,high,pos)
if (n%2==0):
    print (segmentedtreearr.count(k)+1)
else:
    print (segmentedtreearr.count(k))

现在arr = [1,1,1,1,4,5,1]如此不同的可能组合，总和等于k=2可以使用索引[1,1]和(0,1)使用索引[1,1]和(1,2)使用索引[1,1]，但我得到2作为输出虽然我的实现是正确的。

Answer 1

当你有一个绝对点时，段树很适合查找范围，但在你的情况下，你有一个你正在寻找的相对量（一个总和）。

您的代码缺少一对位于树的两个不同分支中的代码：

(2,3)

可以想象，较大的总和可以跨越几个分支（例如sum = 7）。没有简单的方法可以利用这棵树来回答这个问题。

通过列表的简单迭代，使用两个索引（范围的左侧和右侧），当总和太大时递增左侧索引，当它太小时递增右侧索引，则更容易。这假定输入列表中的所有值都是正数，这在您对hackerrank的引用中说明：

Answer 2

这是一个丢弃树方法的O（n）解决方案。它使用来自

def count_segments_with_sum(lst, total):
    i = 0
    count = 0
    for j, v in enumerate(lst):
        total -= v
        while total < 0: 
            total += lst[i]
            i += 1
        count += not total
    return count

print(count_segments_with_sum([1,1,1,1,4,5,1], 2)) # -> 3

的accumulate和groupby以及来自itertools的merge：

它不是很优化。我的重点是展示原理和使用可矢量化的组件。

heapq

结果：

import itertools as it, operator as op, heapq as hq
arr=[1,1,1,1,4,5,1]
k = 2
N = len(arr)

# compute cumulative sum (starting at zero) and again shifted by `-k`
ps = list(it.chain(*(it.accumulate(it.chain((i,), arr), op.add) for i in (0,-k))))

# merge the cumsum and shifted cumsum, do this indirectly (index based); observe that any eligible subsequence will result in a repeated number in the merge
idx = hq.merge(range(N+1), range(N+1, 2*N+2), key=ps.__getitem__)
# use groupby to find repeats
grps = (list(grp) for k, grp in it.groupby(idx, key=ps.__getitem__))
grps = (grp for grp in grps if len(grp) > 1)
grps = [(i, j-N-1) for i, j in grps]

一些更详细的解释：

1）我们建立序列ps = {0，arr_0，arr_0 + arr_1，arr_0 + arr_1 + arr_2，...}累积和的arr。这很有用，因为一段元素的总和可以写成ps中两个项之间的差异。

2）特别是，与[(0, 2), (1, 3), (2, 4)] 相加的连续子序列将对应于ps的一对元素，其差异为k。为了找到那些我们制作ps的副本并从每个元素中减去k。因此，我们需要找到ps和移位ps中的数字。

3）因为ps和ps移位被排序（假设arr的项是正的），ps和ps移位的数字可以使用k在O（n）中找到，merge将这些对彼此相邻。如果我没记错的话，合并将保证稳定，所以我们可以依赖ps中的元素首先出现在任何这样的对中。

4）仍然需要找到我们使用groupby做的对。

5）但是等一下。如果我们直接这样做，我们最终得到的是一对相等的值。如果你只是想把它们算得那么好，但是如果我们想要实际的子列表，我们必须间接地进行合并，使用key kwd arg，其工作方式与sorted相同

6）因此我们创建两个索引范围并使用list.__getitem__作为关键函数，因为我们有两个列表但只能传递一个键，我们首先连接列表。因此，第一和第二列表中的索引是唯一的。

7）结果是一个索引列表idx，使得ps [idx [0]]，ps [idx [1]]，...被排序（程序中的ps是ps，ps-k已经粘贴到它上面）使用与之前我们可以间接地在idx上进行groupby相同的关键功能。

8）然后我们丢弃所有只有一个元素的组，剩下的对则转移回第二个索引。