和为 K 的子数组

原题链接

使用的方法

• Map.containsKey(): 判断 Map 中是否包含指定的键。
• Map.getOrDefault(): 获取指定键的值，如果键不存在则返回默认值。

解题思路

• 使用前缀和和哈希表解决该问题。
• 初始化一个哈希表 map 来记录前缀和及其出现次数，并添加前缀和为0的取款。
• 遍历数组 nums，计算当前的前缀和 pre。
• 对于每个前缀和 pre，检查哈希表中是否存在 pre - k，如果存在，说明从之前的某个位置到当前的位置的子数组的和为 k，将其出现次数加到计数器 count 中。
• 将当前的前缀和 pre 加入哈希表中，更新其出现次数。
• 最后返回计数器 count 的值，即满足条件的子数组的数量。

代码实现

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