本文主要是介绍【力扣 Hot100 | 第八天】4.23(和为K的子数组),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.和为K的子数组
1.1题目
给你一个整数数组 nums
和一个整数 k
,请你统计并返回 该数组中和为 k
的子数组的个数 。
子数组是数组中元素的连续非空序列。
- 示例一:
输入:nums = [1,1,1], k = 2
输出:2
- 示例二:
输入:nums = [1,2,3], k = 3
输出: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;}
这篇关于【力扣 Hot100 | 第八天】4.23(和为K的子数组)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!