[Python]This is what interviewer is expecting, prefix suffix array, clean code
Hint made the solution quite clear, you can get 2 lists that contain prefix shortest lengths and suffix shortest lengths, the result is just simply minimal of s
Hint made the solution quite clear, you can get 2 lists that contain prefix shortest lengths and suffix shortest lengths, the result is just simply minimal of sum(prefix[i], suffix[i+1]) for i in [0, n-2]. I don\'t like those dirty tricks that trying to avoid hashmap, most of those implementations are hard to understand and maintain, I don\'t expect to see those in my everyday work.\n```\nclass Solution:\n    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n\t    # prefix shortest length read from left to right [3,1,5,2,1]3 -> [1, 1, 1, 1, 1]\n        leftmin = self.getMinArr(arr, target, True)\n\t\t# suffix shortest length read from right to left [3,1,5,2,1]3 -> [1, 2, 2, 2, max]\n        rightmin = self.getMinArr(arr, target, False)\n        res = sys.maxsize\n        for i in range(0, len(arr) - 1):\n            if max(leftmin[i], rightmin[i + 1]) != sys.maxsize: # no overlap for i and i + 1\n                res = min(leftmin[i] + rightmin[i + 1], res)\n        return res if res < sys.maxsize else -1\n    \n    def getMinArr(self, arr: list, target: int, right: bool) -> None:\n        res = [sys.maxsize] * len(arr)\n        cursum = 0\n        nummap = {0: 0}\n        # if it\'s reading from right to left, then reverse input array\n        nums = arr if right else arr[::-1]\n        for i, num in enumerate(nums):\n            if i > 0: # min length is the same with previous one before calculation\n                res[i] = res[i - 1]\n            cursum += num\n            if cursum - target in nummap: # get target, calculate minimal length\n                curlen = i - nummap[cursum - target] + 1\n                res[i] = min(res[i], curlen)\n            nummap[cursum] = i + 1\n        if not right: # reverse result array if it was reading from right to left\n            res.reverse()\n        return res\n```
[]