Subarray with Given Sum

The following question was asked during a coding interview for Amazon:

You are given an array of numbers (non-negative). Find a continuous subarray of the list which adds up to a given sum.

alt

# Solve the problem here

'''
1. Clearly state the problem and identify input and output formats.
2. Create some test cases
    - Generic Cases,
    - Subarray at the start,
    - Subarray at the end,
    - Single element,
    - No Subarrayexits,
    - More than one subarray exists.
3. Try all subarrays
4. (Optional) Implement brute force solution.
5. Analyze the complexity and identify inefficiency.
6. Apply the right technique and repeat step 3 to 6
'''

'\n1. Clearly state the problem and identify input and output formats.\n2. Create some test cases\n    - Generic Cases,\n    - Subarray at the start,\n    - Subarray at the end,\n    - Single element,\n    - No Subarrayexits,\n    - More than one subarray exists.\n3. Try all subarrays\n4. (Optional) Implement brute force solution.\n5. Analyze the complexity and identify inefficiency.\n6. Apply the right technique and repeat step 3 to 6\n'

test0 = {
    'input': {'arr': [1,7,4,2,1,3,11,5], 'target': 10},
    'output': (2, 6)
}

test1 = {
    'input': {'arr': [4,2,1,3,11,5], 'target': 10},
    'output': (0, 4)
}

test2 = {
    'input': {'arr': [1,7,4,2,1,3], 'target': 10},
    'output': (2, 6)
}

test3 = {
    'input': {'arr': [], 'target': 10},
    'output': (None, None)
}

tests = [test0, test1, test2, test3]

Solution

Test case:

def subarray_sum1(arr, target):
    n = len(arr)
    for i in range(n):
        for j in range(i, n+1):
            if sum(arr[i:j]) == target:
                return i, j
    return None, None