查找总和等于给定值的子数组的个数

Question

我试图理解一个程序，其任务是找出有多少个子数组的总和等于给定值。我获取的复杂度为 O(N) 的工作代码：static int findSubarraySum(int arr[], int K) {    Map<Integer, Integer> prevSum = new HashMap<>();    int res = 0;    int currsum = 0;    for (int i = 0; i < arr.length; i++) {        currsum += arr[i];        if (currsum == K)            res++;        if (prevSum.containsKey(currsum - K))            res += prevSum.get(currsum - K);        Integer count = prevSum.get(currsum);        if (count == null)            prevSum.put(currsum, 1);        else            prevSum.put(currsum, count + 1);    }    return res;}public static void main(String[] args) {    int arr[] = {10, 2, -2, -20, 10};    int sum = -10;    int n = arr.length;    System.out.println(findSubarraySum(arr, sum));}我无法理解以下代码背后的逻辑：            if (prevSum.containsKey(currsum - K))                   res += prevSum.get(currsum - K);  上面代码中的 HashMap 如何有助于获得正确的结果。

Answer 1

prevSum[i]包含从第一个元素开始且总和为 的连续子数组的数量i。例如，对于 array 3, 4, 2, -4, 2，条目如下所示：

prevSum[3] = 1  // { { 3 } }

prevSum[5] = 1  // { { 3, 4, 2, -4 } }

prevSum[7] = 2  // { { 3, 4 }, { 3, 4, 2, -4, 2} }

prevSum[9] = 1  // { { 3, 4, 2 } }

如果当前前缀总和currsum为10，并且正在查找总和为 的子数组K=3，则需要删除以第一个元素开头的子数组，并总和为 ，7以获得总和为 的适当子数组3。例子：

3, 4, 2, -4, 2, 1, 2, -5, 2

                   ^

|------------------|

              currsum = 10

|--|  -> sums to 7

     |-------------| -> sums to 3

|------------| -> sums to 7

                |--| -> sums to 3

因此，在这个位置，您发现了两个可能的子数组，其总和为K。因此，res += prevSum.get(currsum - K).