Java 2Sum on Prefix Sum
1, acc[i] is sum of prefix array ending at i - 1;\n2, using dp[i] to remember min length of valid subarrays ending at i - 1;\n3, using map to remember all prefi
1, acc[i] is sum of prefix array ending at i - 1;\n2, using dp[i] to remember min length of valid subarrays ending at i - 1;\n3, using map to remember all prefix sum\'s index; (see 2 Sum);\nacc[i] - target == acc[j] then: acc[i] - acc[j] == target \n4, compare everytime we find a new subarray, which will cover all cases.\n```\n    public int minSumOfLengths(int[] arr, int target) {\n        int n = arr.length, acc[] = new int[n + 1], dp[] = new int[n + 1], minLen = Integer.MAX_VALUE, res = minLen;\n        Map<Integer, Integer> map = new HashMap<>();\n        for (int i = 0; i < acc.length; i++) {\n            if (i > 0) acc[i] = acc[i - 1] + arr[i - 1];\n            if (map.containsKey(acc[i] - target)){\n                int preIdx = map.get(acc[i] - target);\n                minLen = Math.min(minLen, i - preIdx);\n                if (dp[preIdx] < Integer.MAX_VALUE) res = Math.min(res, i - preIdx + dp[preIdx]);\n            }\n            map.put(acc[i], i); // empty array\n            dp[i] = minLen;\n        }\n        return res < Integer.MAX_VALUE ? res : -1;\n    }\n```
[]