Leetcode 560 前缀和+哈希表

Leetcode 560 前缀和+哈希表

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

思路分析

前置知识

前缀和不多介绍

算法思路

1. 求加到当前下标i元素的前缀和prefixSum，即sum（num[0:i]）
2. 要求以当前元素为结尾和为k的个数，即求i元素之前的前缀和为 prefixSum - k 的个数
3. 故需要哈希表存储到当前元素之前元素结尾的前缀和为x的个数
4. 更新哈希表，将前缀和为prefixSum的个数更新，如果之前不存在value设为1，存在就在此基础上加1。之前可能存在前缀和为prefixSum，因为元素的值可能为负数

难点：哈希表存储的是什么？

加入当前遍历到的元素下标为i
哈希表存放的就是：
sum（num[0:1]）的个数
sum（num[0:i2）的个数
sum（num[0:3]）的个数
…
sum（num[0:i-1]）的个数

代码

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int prefixSum = 0;
        int count = 0; //结果集
        for(int i = 0; i < nums.length; i++){
    
            prefixSum += nums[i];

            //求以当前元素为结尾的和为k的结果，累加到结果集上
            count += map.getOrDefault(prefixSum - k, 0);

            //更新map
            map.put(prefixSum, map.getOrDefault(prefixSum,0)+1);
        }

        return count;
   
    }
}