C++ Sliding Window + Prefix Sum + DP Solution O(N)
Runtime: 108 ms, faster than 76.46% of C++ online submissions for Find Two Non-overlapping Sub-arrays Each With Target Sum.\nMemory Usage: 77 MB, less than 65.7
Runtime: 108 ms, faster than 76.46% of C++ online submissions for Find Two Non-overlapping Sub-arrays Each With Target Sum.\nMemory Usage: 77 MB, less than 65.79% of C++ online submissions for Find Two Non-overlapping Sub-arrays Each With Target Sum.\n\n```\nFinding target sum sub-array can be done using Sliding Window and Prefix Sum approach easily. \nChallenge is tracking the total min length of 2 target sum subarray who has min length and there is where DP is needed. \nWhat to store in DP so that we can get the min length non-overlapping array while\nwe find a target subarray 2nd time ? We can store the min length of possible target sum subarray\nin DP and so we can use that later to calculate total min length 2 target sum subarray when we find\ntarget sum subarray again where DP[first-1] will return a previous non-overlapping taregt sum subarray min length.\n```\n\n**NOTE: Below sliding window code iteration is index 1 based.**\n\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        \n        int n = arr.size();\n        \n        // track prefix sum of array \n        vector<int>sum(n+1,0);\n        \n        // track the min length target sum subarray till last pointer\n        vector<int>dp(n+1,INT_MAX);\n        \n        sum[0] = 0;\n        \n        // first pointer of the window \n        int first = 1;        \n        \n        // result min length sum of 2 target sum sub array\n        int min_length_sum = INT_MAX;\n        \n        // current window length\n        int curr_len = 0;\n        \n        // min length target sum subarray till last pointer\n        int min_len = INT_MAX;\n        \n        // loop through array and check target sum subarray and previous min length target sum subarray\n        for(int last=1;last<=n;last++)\n        {\n            // update prefix sum for current last pointer\n            sum[last] = sum[last-1] + arr[last-1];\n            curr_len++;\n            \n            // shrink window until window sum <= target \n            while((sum[last] - sum[first-1]) > target)\n                first++,curr_len--;\n            \n            // check for previous valid target sum subarray of min length if current window sum == target\n            if((sum[last] - sum[first-1])==target)\n            {\n                // if previous target sum subarray exists then update min_length_sum\n                // if no previous target sum subarray exists then dp[first-2] will be INT_MAX\n                // dp[first-2] returns min length of target sum subarray which has last < current first\n                if(first>1 && dp[first-2]!=INT_MAX)\n                    min_length_sum = min(min_length_sum,(dp[first-2] + curr_len));\n                \n                // update min length only any target sum subarray found \n                min_len = min(min_len,curr_len);                                        \n            }\n            \n            // update DP[last-1] with min_len which stores the min length of possible target sum subrray till last\n            dp[last-1] = min_len;\n        }\n        \n        // no result found if min_length_sum is INT_MAX\n        return min_length_sum==INT_MAX?-1 : min_length_sum;\n    }\n};\n```
['Array', 'Dynamic Programming', 'C', 'Sliding Window', 'Prefix Sum']