题目描述

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

样例

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

算法1

(暴力枚举) $O(n^2)$

1.从1到n枚举i作为每个子数组的结尾，求出前缀和数组sum，为了防止越界将下标从1开始

2.从1到j枚举j作为i结尾子数组的开头，j<=i,利用前缀和公式sum[i]-sum[j-1]求出连续j-i数组的和

3.两重循环的过程中累加sum[i]=sum[j-1]+k的数组个数

C++ 代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
    int n=nums.size();
    int ans=0,sum[n+1];
    sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+nums[i-1];
        for(int j=1;j<=i;j++)
        if(sum[i]==sum[j-1]+k)
        ans++;
    }
    return ans;
    }
};

算法2

(哈希表) $O(n)$

1. 在1中判断sum[i]==sum[j-1]+k时，可以在循环i的时候求出对应的前缀和s，将前缀和作为key存入hash表
   对于每个i能匹配的j的个数则可以通过hashs[s-k]求出

2.注意对于0-i的前缀和sum[i]-sum[j-1],j=0,sum[-1]越界，但是按照定义sum[-1]=0,即hash[0]已经出现一次，因此
 初始化hash[0]=1;

C++ 代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
    int n=nums.size();
    int ans=0,s=0;
    unordered_map<int,int> hash;

    hash[0]=1;
    for(int i=0;i<n;i++)
    {
        s+=nums[i];
        ans+=hash[s-k];
        hash[s]++;
    }
    return ans;
    }
};