Pythonic way of checking if indefinite # of consec elements in list sum to given value

Question

Having trouble figuring out a nice way to get this task done.

Say i have a list of triangular numbers up to 1000 -> [0,1,3,6,10,15,..]etc

Given a number, I want to return the consecutive elements in that list that sum to that number.

i.e.

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

if there's no consecutive numbers that add up to it, return an empty list.

882 --> [ ] 

Note that the length of consecutive elements can be any number - 3,2,6 in the examples above.

The brute force way would iteratively check every possible consecutive pairing possibility for each element. (start at 0, look at the sum of [0,1], look at the sum of [0,1,3], etc until the sum is greater than the target number). But that's probably O(n*2) or maybe worse. Any way to do it better?

UPDATE: Ok, so a friend of mine figured out a solution that works at O(n) (I think) and is pretty intuitively easy to follow. This might be similar (or the same) to Gabriel's answer, but it was just difficult for me to follow and I like that this solution is understandable even from a basic perspective. this is an interesting question, so I'll share her answer:

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

A 3-iteration max solution Another solution would be to start from close where your number would be and walk forward from one position behind. For any number in the triangular list vec, their value can be defined by their index as:

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

The division between the looking-for sum value and the length of the group is the average of the group and, hence, lies within it, but may as well not exist in it. Therefore, you can set the starting point for finding a group of n numbers whose sum matches a value val as the integer part of the division between them. As it may not be in the list, the position would be that which minimizes their difference.

# 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])

Returns

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

Answer 2

This seems like an algorithm question rather than a question on how to do it in python.

Thinking backwards I would copy the list and use it in a similar way to the Sieve of Eratosthenes. I would not consider the numbers that are greater than x. Then start from the greatest number and sum backwards. Then if I get greater than x, subtract the greatest number (exclude it from the solution) and continue to sum backward. This seems the most efficient way to me and actually is O(n) - you never go back (or forward in this backward algorithm), except when you subtract or remove the biggest element, which doesn't need accessing the list again - just a temp var.

To answer Dunes question:

Yes, there is a reason - to subtracts the next largest in case of no-solution that sums larger. Going from the first element, hit a no-solution would require access to the list again or to the temporary solution list to subtract a set of elements that sum greater than the next element to sum. You risk to increase the complexity by accessing more elements.

To improve efficiency in the cases where an eventual solution is at the beginning of the sequence you can search for the smaller and larger pair using binary search. Once a pair of 2 elements, smaller than x is found then you can sum the pair and if it sums larger than x you go left, otherwise you go right. This search has logarithmic complexity in theory. In practice complexity is not what it is in theory and you can do whatever you like :)