Subarray with Given Sum

# Test

l1=[1,7,4,2,1,3]
# Star Index is i and end index is j
i, j =2, 6
l1[2:6]

sum(l1[2:6])

# Solve the problem here

# Input
arr0 = [1,7,4,2,1,3, 11,5]

target0 = 10

# Output
output0= 2,6

# Function signature
def subarray_sum(arr, target):
    pass

# Create all the cases the function should be able to handle

"""
1.Generic array where rhe subarray is the center
2. Subarray could be at the start
3.Subarray could be at the end
4. There is no subarray that adds up to 10
5.You have a few zeros in the list
6. There are multiple subarrays with the same sum
7. The array is empty
8. The subarray is a single element
Note : Array = list and each sub arry is defined by an index

"""
# Write the code

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):
            # Check if subarray sum equal target
            if sum(arr[i:j]) == target:
                # answer found
                return i, j
    return None, None # if not let's return None, None


# Optimization
 # maintain a running sum for inner loop
 # when sum exceeds target, break inner loop

def subarry_sum2(arr, target):
    n = len(arr)
    # i goes from 0 to n-1
    for i in range(0, n):
        s = 0 # running sum
        # j goes from i to n
        for j in range(i, n+1):
            if s == target:
                return i,j
            elif s > target:
                break
            if j < n:
                s+= arr[j]
    return None, None

# Most Optimized solution
def subarray_sum3(arr, target):
    n = len(arr)
    i, j, s = 0, 0, 0
    while i < n and j <= n+1:
        if s == target:
            return i, j
        elif s < target:
            if j<n :
                s += arr[j]
            j += 1
        elif s > target:
            s -= arr[i]
            i += 1
    return None, None