##Problem

Given an array and a number \$t\$, write a function that determines if there exists a contiguous sub-array whose sum is \$t\$.

Source (Note that the URL may not link to the exact problem as it's from a quiz site, and questions seem to be randomly generated).

I was able to come up with a \$O(n^2)\$ solution, and further thinking hasn't improved upon it:

def substring_sum(lst, target):
 sums = []
 for val in lst:
 if val == target:
 return True
 for idx, _ in enumerate(sums):
 sums[idx] += val
 if sums[idx] == target:
 return True
 sums.append(val)
 return False

Problem

Given an array and a number \$t\$, write a function that determines if there exists a contiguous sub-array whose sum is \$t\$.

Source (Note that the URL may not link to the exact problem as it's from a quiz site, and questions seem to be randomly generated).

I was able to come up with a \$O(n^2)\$ solution, and further thinking hasn't improved upon it:

def substring_sum(lst, target):
 sums = []
 for val in lst:
 if val == target:
 return True
 for idx, _ in enumerate(sums):
 sums[idx] += val
 if sums[idx] == target:
 return True
 sums.append(val)
 return False