LeetCode subarray-sum-equals-k题解 前缀和+Hash表+枚举——线性做法
2024-09-06 21:01:39
文章目录
题意
给定一个数组，求连续的子数组的和为k的子数组个数。
思路
连续子数组的和sum[i,j]
sum[i,j]=∑k=ijAk(i<j)sum[i,j]=\sum_{k=i}^jA_k(i<j)sum[i,j]=∑k=ijAk(i<j)
即数组第i个数到第j个数的子数组的和。
sum[i,j]=sum[j]−sum[i−1]sum[i,j]=sum[j]-sum[i-1]sum[i,j]=sum[j]−sum[i−1]其中sum[i]sum[i]sum[i]是前i个数的前缀和。
另子数组的和固定为k,则右边两个数只需要每一个，就可以确定另一个数的取值。
假设我们把前一个sum的下标记为r,后一个记为l.
若我们枚举l，我们有了如下需求：
sum数组中，下标大于l且值为sum[l]+k的个数是多少？
因此我们可以控制l的枚举顺序为从后往前，并且用hash表维护自l往后的sum[i]中的所有<sum值，个数>以应对此查询并且快速更新hash表。
同理，可以从前往后枚举r,用hash表维护下标小于r的所有的<sum值，个数>……
源码
class Solution {
public int subarraySum(int[] nums, int k) {
int len = nums.length;
//key:sum,value:the count of sum[i] where i<r
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
map.put(0,1); // sum[-1]=0
int count = 0;
for (int r = 0,r_sum = 0;r < len; ++r) {
r_sum += nums[r];
int l_sum = r_sum-k;
if (map.containsKey(l_sum))
count += map.get(l_sum);
if (map.containsKey(r_sum))
map.put(r_sum,map.get(r_sum)+1);
else
map.put(r_sum,1);
}
return count;
}
}
结果记录
- 19ms
- 82.65%
- 40.1MB
- 100.0%
最新文章
- CentOS 6忘记密码解决办法，root和普通用户均可
- SQL笔记1：SELECT及SELECT高级应用
- 关于CSS的那些事？
- Hadoop入门进阶课程3--Hadoop2.X64位环境搭建
- HDU5072 容斥原理
- 中国电信某站点JBOSS任意文件上传漏洞
- GOICE项目初探
- VS2010 自动关闭的问题解决方法
- 【转载】mysqldump的single-transaction和master-data
- 自定义 Layout布局 UICollectionViewLayout
- Asp.net MVC4高级编程学习笔记-模型学习第四课基架与模型绑定20171027
- 玲珑学院-ACM比赛1014 - Absolute Defeat
- 移动端头部固定,上划逐渐透明 (vue)
- leetcode笔记--水箱问题
- python基础之从认识python到python的使用
- Linux服务器---邮件服务openwebmail配置
- 一次mysql数据关于union+concat用法的记录
- JeeWx捷微3.1小程序版本发布，支持微信公众号，微信企业号，支付窗——JAVA版开源微信管家
- 华为笔试——C++字符串四则运算的实现
- PowerDesigner使用教程【转】