当前位置:网站首页>leetcode-560:和为 K 的子数组
leetcode-560:和为 K 的子数组
2022-07-07 08:18:00 【菊头蝙蝠】
leetcode-560:和为 K 的子数组
题目
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
示例 2:
输入:nums = [1,2,3], k = 3
输出:2
解题
方法一:前缀和(超时)
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n=nums.size();
vector<int> preSums(n+1);
for(int i=0;i<nums.size();i++){
preSums[i+1]=preSums[i]+nums[i];
}
int count=0;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
if(preSums[i]-preSums[j]==k){
count++;
}
}
}
return count;
}
};
方法二:前缀和+哈希表
红色部分就是我们要求的和为k的子数组
如果当前遍历到的前缀和是presum,那么只要知道presum-k的个数就行了,对最后结果加上presum-k的个数
通过map去维护一个前缀和 的个数
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> map;
map[0]=1;//前缀和为0的个数为1
int preSum=0;
int count=0;
for(int num:nums){
preSum+=num;
if(map.count(preSum-k)){
//加上前缀和为preSum-k的个数
count+=map[preSum-k];
}
map[preSum]++;
}
return count;
}
};
边栏推荐
- ES6中的函數進階學習
- Fiddler simulates the interface test
- mysql插入数据创建触发器填充uuid字段值
- [second on] [jeecgboot] modify paging parameters
- 对word2vec的一些浅层理解
- Appx code signing Guide
- When there are pointer variable members in the custom type, the return value and parameters of the assignment operator overload must be reference types
- Factorial implementation of large integer classes
- 基于HPC场景的集群任务调度系统LSF/SGE/Slurm/PBS
- Apprentissage avancé des fonctions en es6
猜你喜欢
基于HPC场景的集群任务调度系统LSF/SGE/Slurm/PBS
【acwing】786. Number k
LLVM之父Chris Lattner:为什么我们要重建AI基础设施软件
5个chrome简单实用的日常开发功能详解,赶快解锁让你提升更多效率!
mysql插入数据创建触发器填充uuid字段值
[sword finger offer] 42 Stack push in and pop-up sequence
Fiddler break point
How to cancel automatic saving of changes in sqlyog database
电表远程抄表拉合闸操作命令指令
The method of word automatically generating directory
随机推荐
Postman interface test VII
Learning records - high precision addition and multiplication
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
Postman interface test VI
Some properties of leetcode139 Yang Hui triangle
LeetCode 练习——113. 路径总和 II
Several schemes of building hardware communication technology of Internet of things
555电路详解
嵌入式背景知识-芯片
Word自动生成目录的方法
Guide de signature du Code Appx
Adb 实用命令(网络包、日志、调优相关)
The variables or functions declared in the header file cannot be recognized after importing other people's projects and adding the header file
[牛客网刷题 Day6] JZ27 二叉树的镜像
1323:【例6.5】活动选择
ORM model -- associated fields, abstract model classes
HAL库配置通用定时器TIM触发ADC采样,然后DMA搬运到内存空间。
UnityWebRequest基础使用之下载文本、图片、AB包
基于HPC场景的集群任务调度系统LSF/SGE/Slurm/PBS
Trajectory planning for multi-robot systems: Methods and applications 综述阅读笔记