(Brilliant.org) Arrays Intermediate 3: Contiguous Knapsack

Question

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

Answer 1

You are currently calculating the sum of all possible subarrays. A different approach is to imagine a sliding window on the array. If the sum of the elements in this window is smaller than the target sum, you extend the window by one element, if the sum is larger, you start the window one element later. Obviously, if the sum of the elements within the window is the target, we are done.

This algorithm only works if the array contains only non-negative numbers (as seems to be the case here when looking at the possible answers).

Here is an example implementation:

def contiguous_sum(a, target):
    start, end = 0, 1
    sum_ = sum(a[start:end])
    # print(start, end, sum_)
    while sum_ != target and start < end < len(a):
        if sum_ < t:
            end += 1
        else:
            start += 1
            if start == end:
                end += 1
        sum_ = sum(a[start:end])
        # print(start, end, sum_)
    return sum_ == target

This algorithm can be further improved by only keeping a running total, from which you add or subtract:

def contiguous_sum2(a, t):
    start, end = 0, 1
    sum_ = a[0]
    #print(start, end, sum_)
    while sum_ != t and start < end < len(a):
        if sum_ < t:
            sum_ += a[end]
            end += 1
        else:
            sum_ -= a[start]
            start += 1
            if start == end:
                sum_ += a[end]
                end += 1
        #print(start, end, sum_)
    return sum_ == t

The implementation can be streamlined further by using a for loop, since we actually only loop once over the input array, as recommended in the comments by @Peilonrayz:

def contiguous_sum_for(numbers, target):
    end = 0
    total = 0
    for value in numbers:
        total += value
        if total == target:
            return True
        while total > target:
            total -= numbers[end]
            end += 1
    return False

All three functions are faster than your algorithm for random arrays of all lengths (containing values from 0 to 1000 and the target always being 100):

Answer 2

It is possible to do better than the \$O(n^2)\$ of my original solution and solve it in linear time by using a set to store the sums at each point and comparing if the sum at this point minus the target is in the set. However this solution uses \$O(n)\$ space:

def substring_sum(lst, target):
    sm = 0
    sums = {sm}
    for val in lst:
        sm += val
        if sm - target in sums:
            return True
        sums.add(sm)
    return False