方法一:枚举

int cnt=0;
for(int i=0;i<numsSize;i++)
{
int sum=0;
for(int j=i=j>=0;j--)
{
sum+=nums[j];
if(sum==target)cnt++;
}
}
return cnt;

时间复杂度O(n*n) 对于每个i我们需要循环所有的j 这还可以再进一步优化!

方法二:哈希表+前缀和

C++源代码如下 确实很方便

class Solution {

public:

    int subarraySum(vector<int>& nums, int k) {

       unordered_map<int ,int> mp;

       mp[0]=1;

       int count=0,pre=0;

       for(auto&x:nums)//遍历数组

       {

            pre+=x;//前缀和

            if(mp.find(pre-k)!=mp.end())//寻找key

            {

                count+=mp[pre-k];

            }

            mp[pre]++;

       }

       return count;

    }

};

也可用C语言数组模拟Hash表!!!

#define HASH(n) hashTable[n+10000000]

//强行使下标不可能为负数

int subarraySum(int* nums, int numsSize, int k)

{

    int hashTable[20000001] = {0};

    int pre = 0;

    int count = 0;

    HASH(0)++;

    for (int i = 0; i < numsSize; i++) {

        pre += nums[i];

        if (HASH(pre – k))

            count+=HASH(pre-k);

        HASH(pre)++;

    }

    return count;

}