Write a function which Given an list of integers arr and an integer target, find two non-overlapping sub-arrays of arr each with sum equal target


Topic: Write a function which Given an list of integers arr and an integer target, find two non-overlapping sub-arrays of arr each with sum equal target

Solution

from collections import defaultdict
def minSumOfLengths(arr, target):
    hashTable = defaultdict(int)
    hashTable[0] = -1
    summation = 0
    for i in range(len(arr)):
        summation = summation + arr[i]
        hashTable[summation] = i
        
    summation = 0
    minimumLeft = float('inf')
    result = float('inf')
    for i in range(len(arr)):
        summation = summation + arr[i]
        if summation - target in hashTable:
            leftLength = i-hashTable[summation-target]
            minimumLeft = min(minimumLeft,leftLength)
        if summation + target in hashTable and minimumLeft < float('inf'):
            rightLength = hashTable[summation+target]-i
            result = min(result,hashTable[summation+target]-i+minimumLeft)
        
    if result == float('inf'):
        return -1
    return result
	
	



List all Python Programs