力扣560. 和为 K 的子数组

题目链接

力扣560. 和为 K 的子数组

简单方法

除了使用前缀和之外，本题还有一种较为简单的解法，这种解法比较暴力，是对数组进行时间复杂度为 O(n²) 的搜索，每个外层循环都扩大一次内循环的索引范围，每个内层循环都在外层循环指定的索引范围内查找。由于数组中的元素可能为负值，所以不存在对这种方法进一步的优化。

由于此方法很简单，此处直接将代码贴到下面，不做过多解释。

代码

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum =  0;
            for (int j = i; j >= 0; j--) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

耗时较短的方法

耗时比较

在力扣上，使用第一个方法的运行时间大约为 $1100ms$，而使用本方法的运行时间大约为 $25ms$，可见本方法的优越性。

思想

前缀和

前缀和指的是数组前 $i$ 个元素之和。例如 $arr=[1,2,3,4,5]$ 的第一个前缀和为 $1=1$，第二个前缀和为 $1+2=3$，第三个前缀和为 $1+2+3=6$。

前缀和之差

对于同一个数组的两个前缀和，它们的差为构成两个前缀和的子数组之间 较长子数组 多出 较短子数组 的 所有元素之和(这个描述很抽象，请看下面的例子)。比如以下两个子数组：

对于 $arr1$ 和 $arr2$ 这两个子数组构成的前缀和，它们前缀和的差就是 $5+6+7=18$。

为何要使用前缀和？

因为本题求解的是 和为 $k$ 的字数组个数，此时只需要构造前缀和的集合，存储目前为止构成的前缀和 与 构成该前缀和的子数组个数，然后检查这个集合中是否存在一个前缀和 $s$，使得该前缀和减去 $k$ 的值等于它，如果等于，则让结果数增加目前为止构成前缀和 $s$ 的个数。经过这样的操作，就能求出结果。

为何要建立前缀和映射？

因为 $k$ 的范围为 -10⁷ ~ 10⁷，如果使用数组来存储，则占用的内存很大，故需要使用 $Java$ 中的 $HashMap$ 来存储目前为止构成的前缀和 与 构成该前缀和的子数组个数。

前缀和映射需要一个为0的前缀和

因为前缀和映射中可能存在前缀和恰好等于 $k$ 的情况，此时如果没有为 $0$ 的前缀和，则这些前缀和将被认为是无效的前缀和，从而导致结果小于正确值。

Map对象的getOrDefault()方法

$Map$ 的实现类($Map$ 是一个接口，它有例如 $HashMap$ 等的实现类)对象有一个 $getOrDefault()$ 方法，这个方法的第一个参数为 $key$，如果本集合中不存在该 $key$ 对应的值，则将第二个参数作为返回值。

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 1. 建立前缀和映射，key为前缀和，value为目前为止构成该前缀和的子数组的个数
        Map<Integer, Integer> map = new HashMap<>();

        // 2. 前缀和映射需要一个为0的前缀和
        map.put(0, 1);

        // 3. 遍历数组，构造前缀和映射，并进行查询
        int sum = 0, res = 0; // sum为前缀和的值，res为结果
        for (int num : nums) {
            sum += num; // 构建本轮循环的前缀和
            
            // 如果映射中有一个前缀和s，使得 sum - k = s
            // 则让 结果 += 目前为止构成该前缀和的子数组的个数
            int s = sum - k;
            if (map.containsKey(s)) {
                res += map.get(s);
            }
            
            // 将本轮循环的前缀和放入映射中，若其有对应的value值，则让value加一，否则放入1
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        // 4. 返回结果
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28