Beat 100%, and DP Space << O(N), Time O(N)
In fact, we don\'t need to create all DP cache memory of entire array to store each found length\nbecause only when the known minimal length of window changes(w
In fact, we don\'t need to create all DP cache memory of entire array to store each found length\nbecause only when the known minimal length of window changes(when we find window sum equals target), \nwe need to store it into cache.\nWe can use result to control the minimal sum of the two sub-arrays.\n\nThe cache size of minimal length only depends on \n*how shorter length than target we find first.*  \nIf target is 10 and we find one 10 first, the cache size will be always 1.\nIf we find 9,1 first, the cache size will be always smaller than or equal 2.\n\n**The key point** in short is \nwe only need to store minimal found length and result.\n\n**For example,**\n(cache only stores the new minimum)\nSuppose windows have no overlaps in the following example.\nIf overlap, we just need to find the found length in cache without overlap, \nbut cache is small, so it\'s very fast. I will show it in code.\n```\nRound 0\ncache {}, result {}, found length {}\n```\n```\nRound 1\ncache {2}, result {2}, found length {2}\n```\n```\nRound 2\ncache {2}, result {2+3}, found length {3}\n```\n```\nRound 3\ncache {2}, result {2+2}, found length {2}\n```\n```\nRound 4\ncache {2, 1}, result {2+1}, found length {1}\n```\n```\nRound 5\ncache {2, 1}, result {2+1}, found length {3}\n```\nIn a result, perfermance don\'t change, \nbut we save memory from using all DP cache memory of entire array.\nCode with clear comments as below\n\n```\nclass Solution: # best, 804 ms\n  def minSumOfLengths(self, arr, target):\n    result = inf = 2**31-1\n    i = window = count = 0\n    # preMin: store (index, previous shortest length)\n    preMin = [(-1, inf)]\n\n    # i: window start, j: window end\n    for j, num in enumerate(arr):\n      window += num\n      while window > target:\n        window -= arr[i]\n        i += 1\n      if window == target:\n        # curr: current length\n        curr = j - i + 1\n\t\t\n\t    # early stopping if found two single targets\n        if curr == 1: \n\t\t    count += 1\n            if count == 2: return 2\n\t\t\n        n = 0 \n        # find first minimal length n before window start i\n        for index, length in preMin[::-1]:\n          if index <= i-1: \n            n = length           \n            break\n\t\t\t\n        # update result  \n        if result > curr + n: result = curr + n\n            \n        # update shortest length\n        if curr < preMin[-1][-1]: preMin.append((j, curr))\n\n    return result if result < inf else -1\n```\nwelcome upvote and comments
['Dynamic Programming', 'Sliding Window', 'Prefix Sum', 'Python', 'Python3']