C++ | Sliding Window | DP | O(n)
Let us assume that dp[i] stores the length of the previous shortest subarray whose sum=target before index i. Now suppose after index i, we encounter another su
Let us assume that dp[i] stores the length of the previous shortest subarray whose sum=target before index i. Now suppose after index i, we encounter another subarray of some length l at index r whose sum is also equal to target, then our ans would be the current length, l+dp[r-l] since l length from index r would be used and if there is any subarray whose sum equals target before index (r-l) then we can add that to our ans and that would be some feasible ans and then we take take the minimum of all these feasible answers to find the optimum value.\n\nWe can also guarantee that there would be atleast two such arrays if ans!=INT_MAX by checking if dp[r-l] contains some valid value otherwise this is the first subarray with target sum.\n\nHere is the code:\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int l=0,r=0,csum=0,ans=INT_MAX;\n        vector<int> dp(arr.size(),INT_MAX);\n        for(;r<arr.size();r++){\n            csum+=arr[r];\n            while(csum>target)\n                csum-=arr[l++];\n            if(csum==target){\n                dp[r]=r-l+1;\n                if(l-1>=0 && dp[l-1]!=INT_MAX)\n                    ans=min(ans,dp[r]+dp[l-1]);\n            }\n            if(r-1>=0)\n                dp[r]=min(dp[r-1],dp[r]);\n        }\n        \n        return ans==INT_MAX?-1:ans;\n    }\n};\n```
[]