Continuous sequence against target number

Question

Post problem and my code written in Python 2.7. Any advice for code bugs, performance in terms of algorithm time complexity and code style are appreciated. I did PEB8 self-check in PyCharm.

BTW, a small issue in my code is, I feel this condition end_index == len(numbers) - 1 and cur_sum < target is a bit ugly, but I do not find a better way to remove it for safe boundary check purpose.

'''
Question: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
Example
[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7
'''


def sum_target(numbers, target):
    start_index = 0 # inclusive
    end_index = 0 # inclusive
    cur_sum = numbers[0]
    while end_index < len(numbers):
        if end_index < len(numbers) - 1 and cur_sum < target:
            end_index += 1
            cur_sum += numbers[end_index]
        elif end_index == len(numbers) - 1 and cur_sum < target:
            return False
        elif cur_sum > target:
            cur_sum -= numbers[start_index]
            start_index += 1
        elif cur_sum == target:
            return True

    return False

if __name__ == "__main__":
    print sum_target([23, 5, 4, 7, 2, 11], 20)
    print sum_target([1, 3, 5, 23, 2], 8)
    print sum_target([1, 3, 5, 23, 2], 7)

Answer 1

In case there's no acceptable sequence, you have to go through all the elements anyway, so it can't be lower than O(n), and your code is already O(n).

The only optimization that you could add is a condition where if the current number alone is greater than the expected sum, you skip all values until the one just after the current value.

For instance, suppose you have [2, 3, 4, 25, 7, 8, 9] and you're looking for number 17. You don't want to check 2 + 3 + 4 + 25, 3 + 4 + 25, 4+25, you can skip directly to the index of 7.

Other than that I'd just remove the comments because I don't think they really add anything.

Answer 2

The documentation string you provided at the top of the module would better be placed in the function, and the examples should be formatted as doctests so that they can automatically be checked.

The control flow can be simplified and manual handling of indexes eliminated if you iterate directly over the input list, maintain a deque for the currently considered subsequence, and use an inner while loop for discarding numbers.

from collections import deque

def contains_subsequence_sum(numbers, target):
    '''Given a sequence of positive integers `numbers` and an integer `target`,
    return whether there is a continuous sub-sequence of `numbers` that sums up
    to exactly `target`.

    >>> contains_subsequence_sum([23, 5, 4, 7, 2, 11], 20)  # 7 + 2 + 11 = 20
    True
    >>> contains_subsequence_sum([1, 3, 5, 23, 2], 8)       # 3 + 5 = 8
    True
    >>> contains_subsequence_sum([1, 3, 5, 23, 2], 7)
    False
    '''
    subsequence = deque()
    total = 0

    for number in numbers:
        if total < target:
            subsequence.append(number)
            total += number
        while total > target and subsequence:
            total -= subsequence.popleft()
        if total == target:
            return True

    return False

The original name sum_target suggests that the function returns a number when it actually returns a boolean value (it is a predicate). Such functions tend to have names like "has", "is", "contains", etc. While I'm still not quite happy with it, the name contains_subsequence_sum is a better fit.

Answer 3

I would prefere the following variant, I think one can grasp easier the idea behind the code.

if cur_sum < target:
    if end_index < len(numbers) - 1:
        end_index += 1
        cur_sum += numbers[end_index]
    else
        return False
elif cur_sum > target:
    cur_sum -= numbers[start_index]
    start_index += 1
else:
    assert(cur_sum == target)
    return True