Updated 2 years ago
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.
# Solve the problem here
arr0 = [1,7,4,2,1,3,11,5]
target0 = 10
output0 = 2,6
def subarray_sum(arr, target):
pass
"""
1. Generic array where subarray is in the center
2. Subarray is at the start
3. Subarray is at the end
4. No valid subarray
5. You have a few 0s
6. There are multiple subarrays with the same sum
7. Empty array
8. Subarray is a single element
"""
def subarray_sum1(arr, target):
n=len(arr)
# i goes from 0 to n-1
for i in range(0,n):
# j goes from i to n
for j in range(i, n+1):
if (sum(arr[i:j])) == target:
return i,j
return None, None
# Test the solution here
subarray_sum1(arr0, target0)
(2, 6)
subarray_sum1([4,2,1,3], target0)
(0, 4)
subarray_sum1([1,7,4,2,1,3], 17)
(1, 6)