[C++] O(n) DP and Prefix-Sum solution (one pass)
For each element arr[i], use prefix-sum to find if a valid subarray exists ending at i. If yes, it will start at j = index[sum-target], where sum is the running
For each element ``` arr[i] ```, use prefix-sum to find if a valid subarray exists ending at ```i```. If yes, it will start at ```j = index[sum-target]```, where ```sum``` is the running total. Simply find the length of the shortest valid subarray before the start of this subarray, ```minDP[j]``` and add it to the length of the current valid array, ``` dp[i] = i-j ```. Keep track of the minimum sum of these two lengths.\n\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size();\n        vector<int> dp(n); // dp[i]: length of valid subarray ending at i\n        vector<int> minDP(n); // minDP[i]: length of shortest valid subarray till i\n        unordered_map<int,int> index;  // maps running total to index\n        int mindp = INT_MAX,ans = INT_MAX,sum = 0;\n        index[sum] = -1;\n        for(int i=0;i<n;i++){\n            sum+=arr[i];\n            if(index.find(sum-target)!=index.end()){ // valid subarray\n\t\t\t\tint j = index[sum-target];\n                dp[i] = i-j; // length of current subarray\n                if(j>=0 && minDP[j]!=INT_MAX) \n                    ans = min(ans, dp[i]+minDP[j]);\n            }\n            else dp[i] = INT_MAX; // invalid subarray\n            mindp = min(mindp,dp[i]);\n            minDP[i] = mindp;\n            index[sum] = i;\n        }\n        return ans==INT_MAX? -1:ans;\n    }\n};\n```\n\nTime - ```O(n)```\nSpace - ```O(n)```
['Dynamic Programming', 'Prefix Sum']