Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Solution
我们需要找到所有的区间:
\[nums[i]+...+nums[j]=k \]那么我们使用前缀和 \(prex[i]-prex[j-1]=k\)，那么转变一下：
\[prex[i]-k=prex[j-1] \]所以同样也是 \(prex\)
点击查看代码
class Solution {
private:
unordered_map<int,int> mp;
int prex[20002];
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
int ans=0;
prex[0]=nums[0];
for(int i=1;i<n;i++)prex[i]=nums[i]+prex[i-1];
for(int i=0;i<n;i++){
if(prex[i]==k)ans++;
if(mp.find(prex[i]-k)!=mp.end())ans+=mp[prex[i]-k];
mp[prex[i]]++;
}
return ans;
}
};