首页 > 代码库 > 算法(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