Easy C++ solution in O(n) using DP, and Prefix Sum
Intuition\nThe prefix-sum is used to calculate the valid subarays. The dp[i] stores the minimum length valid subarray till index i. \n\n# Approach\nOn every ite
# Intuition\nThe prefix-sum is used to calculate the valid subarays. The `dp[i]` stores the minimum length valid subarray till index `i`. \n\n# Approach\nOn every iteration, find the running sum (`prefix sum`). If there exists `s-target` already, means that the subarray between `m[s-target] + 1` and till `i` has a sum of `target`. We\'ll then mark this as a valid subarray. Now, for this valid subarray, let `j` be the starting index. If there exists any valid subarray till `j-1`, we may have a result. \n\n# Complexity\n- Time complexity: $$O(n)$$\n\n\n- Space complexity: $$O(n)$$\n\n\n# Code\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        \n        int n = arr.size(), s = 0,result = INT_MAX;;\n        vector<int> dp(n, INT_MAX);     //len of smallest valid subarray ending at i\n        \n        unordered_map<int,int> m;\n        m[0] = -1;\n        for(int i=0;i<n;i++){\n            s += arr[i];\n            if(m.find(s-target) != m.end()){\n                int j = m[s-target] + 1;\n                dp[i] = i - (j) + 1;\n\n                //we also have a previous array\n                if(j> 0 && dp[j - 1] != INT_MAX){\n                    result = min(result, dp[j-1] + dp[i]);\n                }\n            }\n\n            if(i > 0){dp[i] = min(dp[i], dp[i-1]);}\n            m[s] = i;\n        }        \n        \n        return result == INT_MAX ? -1 : result;\n \n    }\n};\n```
['C++']