和为k的子数组
和为k的子数组
1、题目
![image-20240229220749386](https://2hang.oss-cn-beijing.aliyuncs.com/img/202402292208185.png)
2、题解
前缀和+哈希表
前缀和:一个数组的某个下标之前的所有数组元素的和(包含自身)
通常会习惯在前缀和首位放一个0,例如数组\([1,2,3]\),前缀和就为\([0,1,3,6]\),前缀和有助于快速计算某个区间内的和,例如要计算\(i,j\)之间的和:\(nums[i]+nums[i+1]+……+nums[j]\),可以看作是\(nums[0]+nums[1]+……+nums[i]+……+nums[j]\)减去\(nums[0]+nums[1]+……+nums[i-1]\),也可以看作\(preSum[j]-preSum[i-1]\)。
在遍历过程中,统计历史中每一个前缀和出现的次数,然后计算到i位置的前缀和\(presum\)减去目标k在遍历过程中出现的次数,假设出现\(m\)次,代表第i位以前有\(m\)个连续子数组的和为\(presum-k\),这\(m\)个和为\(presum-k\)的连续子数组,每一个都可以和\(presum\)组合成\(presum-(presum-k)=k\).
1 |
|
和为k的子数组
http://example.com/2024/02/29/和为k/