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

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&nbsp; // { { 3 } }prevSum[5] = 1&nbsp; // { { 3, 4, 2, -4 } }prevSum[7] = 2&nbsp; // { { 3, 4 }, { 3, 4, 2, -4, 2} }prevSum[9] = 1&nbsp; // { { 3, 4, 2 } }如果当前前缀总和currsum为10，并且正在查找总和为 的子数组K=3，则需要删除以第一个元素开头的子数组，并总和为 ，7以获得总和为 的适当子数组3。例子：3, 4, 2, -4, 2, 1, 2, -5, 2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;^|------------------|&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currsum = 10|--|&nbsp; -> sums to 7&nbsp; &nbsp; &nbsp;|-------------| -> sums to 3|------------| -> sums to 7&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |--| -> sums to 3因此，在这个位置，您发现了两个可能的子数组，其总和为K。因此，res += prevSum.get(currsum - K).