C++/Python, prefix sum + dynamic programming solution with explanation
First, we can use prefix sum to find left side of array whose right side is at current number and sum is equal to target.\nThe problem is how to find another ar
First, we can use prefix sum to find left side of array whose right side is at current number and sum is equal to ```target```.\nThe problem is how to find another array is not overlapped with this array and sum of two array length is the shortest.\n```dp[i]``` is length of shortest array whose sum is equal to ```target``` before location ```i```.\nSo, if we find a array whose sum is equal to ```target```, ```dp[i] = min(dp[i-1], length)``` else ```dp[i] = dp[i-1]```\n\nThe key is ```dp```, if current number is right side of array whose sum is equal to ```target```, one array length is ``` current index - prefix[cur sum - target]```, another array should be before location ```prefix[cur sum - target] + 1```, so its length is ```dp[prefix[cur sum - target]]```, so two array length is ```current index - prefix[cur sum - target] + dp[prefix[cur sum - target]]```, and track the shortest length is the answer.\n\ne.g. ```[1,1,1,2,1,1,1], target = 3```\n```\nprefix is a mapping from current sum to index.\nidx     -1 0 1 2 3 4 5 6\n         x 1 1 2 1 1 1 3\nsum      0 1 2 4 5 6 7 10\ndp[idx]  m m m 2 2 2 2 1\nans      m m m m m m 5 3\n\nAt arr[5] = 1, current sum is 7, 7 - 3 = 4 in prefix, prefix[4] is 2 which means arr[3~5] is one of both array\nlength of array whose right side at nums[5] is 5 - prefix[4](=index 2) = 3,\nanother array should be before index 3, so length of another array is dp[2] = dp[prefix[4]] = dp[prefix[current sum - target]].\n\n```\ntc is O(n), sc is O(n)\n\n### c++\n```cpp\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int ans = 2 * arr.size(), cur = 0;\n        vector<int> dp (arr.size() + 1, 2 * arr.size());  // because of dp[i-1], add a trivail value be index -1\n        unordered_map<int, int> prefix;\n        prefix[0] = -1;\n        for (int i = 0, leng; i < arr.size(); i+=1) {\n            cur += arr[i];\n            if (prefix.count(cur - target) != 0) {\n                leng = i - prefix[cur - target];\n                dp[i+1] = min(dp[i], leng);\n                ans = min(ans, leng + dp[prefix[cur - target] + 1]);\n                \n            } else dp[i+1] = dp[i];\n            prefix[cur] = i;\n        }\n        return ans != 2 * arr.size()? ans :-1;\n    }\n};\n\n```\n### python\n```python\nclass Solution:\n    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n        prefix = {0: -1}\n        ans = 2 * len(arr)\n        cur = 0 # current sum\n        dp = [2 * len(arr)] * (len(arr) + 1) # because of dp[i-1], add a trivail value be index -1\n        for idx, n in enumerate(arr):\n            cur += n\n            if cur - target in prefix:\n                leng = idx - prefix[cur - target]\n                dp[idx+1] = min(dp[idx], leng)\n                ans = min(ans, leng + dp[prefix[cur - target] + 1])\n            else: dp[idx+1] = dp[idx]\n            prefix[cur] = idx\n        return ans if ans != 2 * len(arr) else -1\n```
['Dynamic Programming', 'C', 'Prefix Sum', 'Python']