通关剑指 Offer——剑指 Offer II 010. 和为 k 的子数组

1.题目描述

剑指 Offer II 010. 和为 k 的子数组

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

示例 1：

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例 2：

输入:nums = [1,2,3], k = 3
输出: 2

2.解题思路与代码

2.1 解题思路

这道题需要求和等于某一个数的连续子数组，那么像这种连续子数组求和的题目首先就可以想到使用前缀和进行求解。我们把前缀和数组记为 sum[] 原数组记为 num[]，前缀和数组有以下两个特性

• 前缀和数组第 i 位的值就是原数组 [0, i] 位所有元素之和
• sum[i]-sum[j] (i>j) 等于原数组 [i+1, j] 上元素之和

基于这两个特性，我们可以知道题目要求的连续子数组和等于 k，其实就是在求前缀和数组上是否存在两个位置 i 和 j （其中 j>i）使得 sum[j]-sum[i]=k，这一点推导出来之后这道题就非常简单了。

我们对上面公式 sum[j]-sum[i]=k 进行变形得到 sum[j]-k=sum[i]，我们在获取前缀和数组的时候是从头到尾遍历原数组 num[]，而这个变形后的公式意义就是当我们求到第 j 位置的前缀和时，在 j 之前是否存在一个前缀和等于第 j 位置的前缀和减 k，每存在一个 sum[i] 等于 sum[j]-k 就统计结果加 1。由于需要在 j 之前查找前缀和，为了减少遍历我们使用一个哈希表来存储之前计算过的前缀和和个数。这里有一点需要注意，前缀和数组需要比原数组多一位，并且前缀和数组的第 0 位置为 0。

以题目示例 nums = [1,1,1], k = 2 为例进行图解。
首先我们对前缀和数组和哈希表进行初始化，前缀和数组位数比原数组多一位存放初始 0，表示此时没有选数字时前缀和是 0，并将 0 放入哈希表中

开始计算前缀和，遍历原数组第一位，此时 sum[1] 等于 1，那么根据前面的公式，我们需要查找第 1 位前面是否存在一个前缀和等于sum[1]-k 即 -1，从哈希表中并没有查找到，于是将 sum[1] 放入哈希表后继续遍历

继续计算前缀和，此时 sum[2] 等于 2，那么就需要看 sum[2] 之前是否存在前缀和等于 sum[2]-2 即 0，从哈希表中能够获取到 0 出现了一次，统计结果加一，并将 sum[2] 放入哈希表中

最后遍历到原数组的第 2 位，此时 sum[3] 等于 3，那么就需要在之前的前缀和中查找是否存在 sum[3]-2 即 1，在哈希表中存在 1，并且只出现了一次，于是结果加一，最终得到结果是 2.

2.2 代码

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        if (nums.length == 1) {
    
            return nums[0] == k ? 1 : 0;
        }
        // 初始化前缀和数组，长度比原数组多一位，并且第 0 位设置为 0
        int[] sum = new int[nums.length + 1];
        sum[0] = 0;
        // 初始化哈希表存放
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int ans = 0;
        for (int i = 1; i < nums.length + 1; i++) {
    
            // 计算前缀和，并计算需要查找的 target
            sum[i] = sum[i - 1] + nums[i - 1];
            int target = sum[i] - k;
            // 从哈希表中读取 target 计入结果中
            ans += map.getOrDefault(target, 0);
            // 将当前位的前缀和存入哈希表
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        return ans;
    }
}

2.3 测试结果

通过测试

3.总结

• 使用前缀和和哈希表进行解答
• 前缀和数组需要初始化使用 0 占位