算法思路

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。

sum[i..j] = nums[0..j] - nums[0..i]

一般会通过哈希表加速查找

代码实现

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