[C++] O(N) solution by prefix sum and DP
precalculate at each position, i, the min length of array with target sum from left and from right respectively. \n\ta. fromLeft[i]: from the leftmost to positi
1. precalculate at each position, i, the min length of array with target sum from left and from right respectively. \n\ta. fromLeft[i]: from the leftmost to position, i, ```(i.e. [0 .. i])```, the min length of the array with target sum\n\tb. fromRight[i]: from the rightmost to position, i, ```(i.e. [i .. n-1])```, the min length of the array with target sum\n2. use DP to find the min sum of length at each pisition, i. ```(i.e. , dp[i] = fromLeft[i] + fromRight[i+1])```\n\ta. consider the minimal sum of two arrays\' length at each index, i. ```(i.e. min sum of length at index i = min length in the range of [0 .. i] + min length in the range of [i+1 .. n-1])```\n\tb. reverse the given array and apply the same subfunction to simply the code.  \n3. complexity \n\ta. Time complexity : O(N)\n\tb. Space complexity: O(N)\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        // from the left, min length of array with sum = target\n        vector<int> left = minLen(arr, target);\n\n        // from the right, min length of array with sum = target\n        vector<int> arrReverse(arr.begin(), arr.end());\n        reverse(arrReverse.begin(), arrReverse.end());\n        vector<int> right = minLen(arrReverse, target);\n        \n        // consider each position to find the min sum of length of the two array with target sum\n        int min_val = arr.size() + 1;\n        int n = arr.size();\n        for(int i = 0; i < arr.size() - 1; ++i) {\n            min_val = min(min_val, left[i] + right[n-1-i-1]);\n        }\n        return min_val == arr.size() + 1 ? -1 : min_val;\n    }\n    \n    // at each position, i, find the min length of array with target sum \n    vector<int> minLen(vector<int> &arr, int target) {\n        int n = arr.size();\n        vector<int> presum(n, 0);\n        unordered_map<int, int> idx;\n        vector<int> ans(n, n + 1);\n        idx[0] = -1;\n        for(int i = 0; i < arr.size(); ++i) {\n            presum[i] = i == 0 ? arr[i] : arr[i] + presum[i-1];\n            int len = arr.size() + 1;\n            if(idx.find(presum[i] - target) != idx.end()) {\n                len = i - idx[presum[i]-target];\n            }\n            idx[presum[i]] = i;\n            ans[i] = i == 0 ? len : min(ans[i-1], len);    \n        }\n        return ans;\n    }\n    \n};\n```
['Dynamic Programming', 'C', 'Prefix Sum']