[C++] O(N) solution with helper arrays and explanation
The problem could be splitted in two subproblems:\n- find all subarrays which sum is equal to target\n- between the valid subarrays, find the two smalles not ov
The problem could be splitted in two subproblems:\n- find all subarrays which sum is equal to target\n- between the valid subarrays, find the two smalles not overlapping\n\nFor the first problem we can easily solve it using the standard approach of prefix sum + helper HashMap with the ending index of previous sums (approach 4 of https://leetcode.com/problems/subarray-sum-equals-k/solution/ )\nEvery time we have a match we can track that we found a matching array of size X starting at the index L and ending at index R. In the index L and R we can directly store the size. We can then linearly calculate what is the smallest array which ends before or which start after a specific index.\n\nFinally we can go over all pair of indexes \'i\' and \'i+1\', checking the sum of the smallest array which ends before \'i\' and which start after \'i+1\'. We can do this because we know that they don\'t overlap\n\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size();\n        unordered_map<int, int> prev;\n        prev[0] = -1;\n        int prevVal = 0;\n        \n        vector<int> matchLeft(n, n + 1), matchRight(n, n + 1);\n        \n        for (int i = 0; i < n; ++i) {\n            // calculate cumulative sum\n            arr[i] += prevVal;\n            prevVal = arr[i];\n            \n            if (prev.count(arr[i] - target)) {\n                // subarray sum matches the target\n                int secondIndex = prev[arr[i] - target];\n                \n                // store the shortest matching array ending in \'i\'\n                if (matchLeft[i] > i - secondIndex)\n                    matchLeft[i] = i - secondIndex;\n                \n                // store the shortest matching array starting in \'secondIndex + 1\'\n                if (matchRight[secondIndex + 1] > i - secondIndex)\n                    matchRight[secondIndex + 1] = i - secondIndex;\n            }\n            prev[arr[i]] = i;\n        }\n        \n        // store the shortest matching array after index \'i\'\n        for (int i = n - 2; i >= 0; --i)\n            matchRight[i] = min(matchRight[i], matchRight[i+1]);\n        \n        int ans = n + 1;\n        int minLeft = matchLeft[0];\n        \n        // for each \'i\' and \'i+1\', calculate the shortest matching array\n        // which ends before \'i\' and the shortest which start after \'i+1\'\n        for (int i = 0; i < n - 1; ++i) {\n            minLeft = min(minLeft, matchLeft[i]);\n            ans = min(ans, minLeft + matchRight[i+1]);\n        }\n        \n        if (ans == n + 1)\n            return -1;\n        \n        return ans;\n    }\n};\n```
[]