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.

• Lin Ma: Thanks for your advice, ChatterOne. Mark your reply as answer.

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.

• Lin Ma: Nice advice and vote up, thanks for the elegant solution mkrieger1.

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

• Lin Ma: Love your advice and code, vote up.