Skip to content

Instantly share code, notes, and snippets.

@rafalio
Created February 27, 2013 17:40
Show Gist options
  • Save rafalio/5049870 to your computer and use it in GitHub Desktop.
Save rafalio/5049870 to your computer and use it in GitHub Desktop.
Contiguous subsequence sum
# 'A' is an unsorted array of integers
# Find any contigous subsequence of A that sums to C.
def cont_subsequence_sum(A, C):
m = dict() # Maps number to index
curSum = 0
m[0] = -1
for i in range(len(A)):
curSum += A[i]
if( (curSum - C) in m ):
answer = [A[j] for j in range(m[curSum-C]+1,i+1)]
return answer
m[curSum] = i
return []
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment