[JAVA] One pass O(N) the simplest solution with explanation
This problem can be divided to two small problems: 1) find all subarray whose sum is equal to target; 2) find two subarrays from the former result which are not
This problem can be divided to two small problems: 1) find all subarray whose sum is equal to target; 2) find two subarrays from the former result which are not overlapping and whose total length is minimum.\n\nFor subproblem 1), we can use sliding window to find all subarray; basically use two pointers, i, j to scan the arr and check the sum between i and j; \n\nFor subproblem 2) we can use an array, e.g. dp to record that for every index i, the shortest length subarray whose sum is equal to target up until index i and including index i itself. \n\nNotice subproblem 2) can be solved along with subproblem 1);  Also the final result can solved along the two subproblem, bascially when we find subarray[i, j], notice the previous non-overlapping subarray length will be dp[i-1], so we can update the result with dp[i-1] + (j - i + 1);\n\n```\nclass Solution {\n    public int minSumOfLengths(int[] arr, int target) {        \n        int result = Integer.MAX_VALUE; // the final result\n        int len = arr.length;\n        int[] dp = new int[len]; //min subarray length so far until the index\n        int i = 0, j = 0; // i is left pointer, j is right pointer\n        int sum = 0;\n        while(j<len) {\n            dp[j] = Integer.MAX_VALUE; // initialize the value\n            sum += arr[j];\n            while(i<len && sum > target) { // move left pointer if sum is larger than target\n                sum -= arr[i];\n                i++;\n            }\n            \n            if(sum == target) {\n                dp[j] = j - i + 1;  // set the dp value to current subarray\n                \n                if(i-1>=0 && dp[i-1] != Integer.MAX_VALUE) // dp[i-1] will the min length of non-overlapping subarray \n                    result = Math.min(dp[j] + dp[i-1], re); \n            }\n            \n            if(j-1>=0)\n               dp[j] = Math.min(dp[j], dp[j-1]); // dp[i] represents the shortest length subarray so far\n            \n            j++;\n        }\n        \n        return result == Integer.MAX_VALUE ? -1 : result;\n        \n    }\n}\n```
['Dynamic Programming', 'Java']