首页 > 代码库 > 算法(10)Subarray Sum Equals K
算法(10)Subarray Sum Equals K
题目:在数组中找到一个子数组,让子数组的和是k。
思路:先发发牢骚,这两天做题是卡到不行哇,前一个题折腾了三天,这个题上午又被卡住,一气之下,中午睡觉,下午去了趟公司,竟然把namespace和cgroup的架构给搞懂了!所以晚上再来攻克这个问题!上午的做法是这样的,设置一个fast指针,一个slow指针,当【slow,fast】中的值大于k的时候,fast++,反之slow++,这种错误的解法误以为数组是有序的,所以是行不通的,那么这道题的解法是什么呢?然后写了下O(n^3)的解法,果不其然,计算超时!!!没办法,只能查资料啦!
真正被接收的答案真是让人始料未及:
int sum = 0;
int n = nums.size();
map<int,int> m;
int res = 0;
for (int i = 0; i < n; i++) {
m[sum]++;
sum += nums[i];
res += m[sum-k];
}
return res;
map是做啥的啊,以【1,1,1】为例吧,第一轮
m[0]=1, sum=1 res=m[1-2=-1]=0;
m[1]=1, sum=1+1=2 res=m[2-2=0]=1;
m[2]=1, sum=2+1=3 res+=m[3-2=1]=1+1=2;
算法(10)Subarray Sum Equals K
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。