LEETCODE ALGORITHM:560. Subarray Sum Equals K

发表于 更新于 分类于 Waline： 阅读次数：

题目

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

1
2
Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

  • The length of the array is in range [1, 20,000].
  • The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

题解

暴力法一定会超时，使用map记录前缀求和次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> m;//保存前n个数求和的数值，一个参数为前n个数求和，第二位为有多少种可能前n个数求和值为该数值
        int tmp=0,ans=0;
        for(int i=0;i<nums.size();++i)
        {
            tmp+=nums[i];
            if(tmp==k) ans++;
            int t=tmp-k;
            if(m.find(t)!=m.end()) ans+=m[t];
            if(m.find(tmp)==m.end()) m[tmp]=1;
            else m[tmp]++;
        }
        return ans;
    }
};