要求以 i 结尾和为 k 的连续子数组个数，要从下标范围 0…i 中统计出符合条件的下标 j 的个数，其中 0 <= i <= j，使得下标范围 j…i 的子数组的和为 k 。

思路分析完，采用暴力解法。定义外层循环慢指针 slow，再定义一个内循环快指针 fast 从当前慢指针 slow 开始向前遍历，统计所有符合 k 的子数组。

代码如下：

class Solution {
    public int subarraySum(int[] nums, int k) {
        
        int count = 0;
        for(int slow = 0; slow < nums.length; slow++){
            int fast = slow;
            int result = 0;
            while(fast >= 0){
                result += nums[fast];
                if(result == k){
                    count++;
                }
                fast--;
            }
        }
        return count;

    }
}

很明显，暴力解法时间复杂度为 O(n²)。

优化方法：前缀和 + 哈希表

暴力解法最大的一个问题就是我们遍历 慢指针 slow 所指的元素时，要把小于它的所有下标都要计算一遍数字和来判断是否符合条件。这就是 O(n²) 时间复杂度的来源。

为了后续分析方便，这里不再称快慢指针，而是用 i 和 j 表示。

定义 pre[i] 是 [0, …, i] 里所有数的和，那么 pre[i] 可以由 pre[i – 1] 递推求出：

pre[i] = pre[i – 1] + nums[i]；

那么将 pre[i – 1] 这一项移到左侧得到的式子代表什么含义呢？

pre[i] – pre[i – 1] = nums[i]；

是不是就是说 [0, …, i] 所有数的和 减去 [0, …, i – 1] 所有数的和的结果是 nums[i] 。那么我们为了求出符合条件的和为 k 的子数组，可以取 [0, …, i] 所有数的和 减去 [0, …, j] 所有数的和 作为判断条件，其中 j <= i。 是的，这就是优化方案。

if(pre[i] – pre[j – 1] == k)

整理一下就是 pre[j – 1] == pre[i] – k 作为判断条件来统计个数。

此时 if 判断逻辑变为：

if (pre[j – 1] == pre[i] – k) {}

思路有了，开始总结一下我们用到了哪些知识点：

前缀和：

对于数组中的任何位置 i ，前缀和 pre[i] 是数组中从第一个元素到第 i 个元素的总和。这意味着如果我们想知道从元素 j 到 i 的子数组的和，可以用 pre[i] – pre[ j – 1] 来计算。

Map 来存储数据：

代码实现中，采用 哈希表来存储每个前缀和出现的次数。通过上面分析的 if 判断条件来快速查找某个符合条件的前缀和是否已经存在，以及它出现的次数。

完整代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
        
        int count = 0; 
        int pre = 0;
        HashMap<Integer, Integer> preMap = new HashMap<>();
        preMap.put(0, 1);
        for(int i = 0; i < nums.length; i++){
            pre += nums[i];
            if(preMap.containsKey(pre - k)){
                count += preMap.get(pre - k);
            }
            preMap.put(pre, preMap.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

这里有个小细节，为什么会有 preMap.put(0, 1)；这行代码，什么含义？

其实我们在统计前缀和的时候，在首次找到子数组和为 k 的时候，pre[i] – k 是 0，如果不加入这行代码，那么就会丢失这首次查到的结果。所以这行代码本意是初始化的作用，记录第一次找到符合结果的子数组。

遍历数组的时候时间复杂度为 O(n)，但是在查找符合条件的子数组的时候是基于 Map 的数据结构，时间复杂度为 O(1)，因此整体的时间复杂度为 O(n)。