检查列表中不定# of consec 元素是否总和为给定值的 Pythonic 方法

Question

找不到完成此任务的好方法。

假设我有一个三角数列表，最大为 1000 -> [0,1,3,6,10,15,..]etc

给定一个数字，我想返回该列表中总和等于该数字的连续元素。

即

64 --> [15,21,28]
225 --> [105,120]
371 --> [36, 45, 55, 66, 78, 91]

如果没有相加的连续数字，则返回一个空列表。

882 --> [ ] 

请注意，连续元素的长度可以是任意数字 - 在上面的示例中为 3、2、6。

蛮力方法将迭代检查每个元素的每个可能的连续配对可能性。 (从0开始，看[0,1]的和，看[0,1,3]的和，等等，直到和大于目标数)。但这可能是 O(n*2) 或者更糟。有什么办法可以做得更好吗？

更新: 好的，所以我的一个 friend 想出了一个在 O(n) 时有效的解决方案(我认为)并且直观上很容易理解。这可能与加布里埃尔的回答相似(或相同)，但我很难理解，而且我喜欢这个解决方案即使从基本角度来看也是可以理解的。这是一个有趣的问题，所以我将分享她的回答:

def findConsec(input1 = 7735):

    list1 = range(1, 1001)
    newlist = [reduce(lambda x,y: x+y,list1[0:i]) for i in list1]

    curr = 0
    end = 2
    num = sum(newlist[curr:end])

    while num != input1:

        if num < input1:
            num += newlist[end]
            end += 1

        elif num > input1:
            num -= newlist[curr]
            curr += 1

        if curr == end:
            return []

    if num == input1:
        return newlist[curr:end]

Answer 1

3 次迭代最大解 另一种解决方案是从靠近您的号码所在的位置开始，然后从后面的一个位置向前走。对于三角列表 vec 中的任何数字，它们的值可以通过它们的索引定义为:

vec[i] = sum(range(0,i+1))

求和值与组长度之间的除法是组的平均值，因此位于其中，但也可能不存在于其中。 因此，您可以将查找和与值 val 匹配的一组 n 个数字的起点设置为它们之间除法的整数部分。由于它可能不在列表中，因此位置将是使它们的差异最小化的位置。

# vec as np.ndarray -> the triangular or whatever-type series
# val as int -> sum of n elements you are looking after
# n as int -> number of elements to be summed
import numpy as np

def seq_index(vec,n,val):
    index0 = np.argmin(abs(vec-(val/n)))-n/2-1 # covers odd and even n values
    intsum = 0 # sum of which to keep track
    count = 0 # counter
    seq = [] # indices of vec that sum up to val

    while count<=2: # walking forward from the initial guess of where the group begins or prior to it
        intsum = sum(vec[(index0+count):(index0+count+n)])
        if intsum == val:
            seq.append(range(index0+count,index0+count+n))
        count += 1
    return seq

# Example

vec = []

for i in range(0,100):
    vec.append(sum(range(0,i))) # build your triangular series from i = 0 (0) to i = 99 (whose sum equals 4950)

vec = np.array(vec) # convert to numpy to make it easier to query ranges

# looking for a value that belong to the interval 0-4590
indices = seq_index(vec,3,4)
# print indices
print indices[0]
print vec[indices]
print sum(vec[indices])

返回

print indices[0] -> [1, 2, 3]
print vec[indices] -> [0 1 3]
print sum(vec[indices]) -> 4 (which we were looking for)