【力扣 Hot100 | 第八天】4.23（和为K的子数组）

1.和为K的子数组

1.1题目

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

子数组是数组中元素的连续非空序列。

• 示例一：

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

• 示例二：

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

1.2解法：前缀和+哈希

1.2.1解法思路

• 核心思想：
  • 使用前缀和的概念：对于数组中的任意连续子数组，可以通过计算前缀和来快速得到该子数组的和。
  • 维护一个HashMap，其中键表示前缀和，值表示该前缀和出现的次数。
  • 在遍历数组过程中，不断更新前缀和，并计算当前前缀和与目标值k的差值，然后查看HashMap中是否存在该差值，若存在，则表示存在和为k的子数组。
• 代码解释：
  • count：用于记录和为k的子数组的数量。
  • pre：用于记录当前的前缀和。
  • mp：HashMap，用于存储前缀和及其出现的次数。
  • 遍历数组nums，对于每个元素：
    • 更新前缀和pre，并计算当前前缀和与目标值k的差值。
    • 若HashMap中存在该差值，则将该差值对应的出现次数累加到count中。
    • 更新HashMap中当前前缀和的出现次数。
  • 最终返回count，即和为k的子数组的数量。
• 举例如下：

1.2.2代码实现

	public int subarraySum(int[] nums, int k) {
        int pre=0;      //前缀和
        Map<Integer,Integer> map=new HashMap<>();   //存放key为前缀和，value为该前缀和出现的情况
        map.put(0,1);   //前缀和为0的情况有1种，即空数组
        int count=0;    //和为k的子数组的总数量
        for(int i=0;i<nums.length;i++){
            pre+=nums[i];
            if(map.containsKey(pre-k)){
                //count 加上 map包含pre与k的差值（）
                count+=map.get(pre-k);
            }
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15