中等 · 子串 · 原题

题目信息

LeetCode #560 · Subarray Sum Equals K

标签：数组、哈希表、前缀和

题目要求

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1
2
输入：nums = [1,1,1], k = 2
输出：2

示例 2：

1
2
输入：nums = [1,2,3], k = 3
输出：2

提示：

  • 1 <= nums.length <= 2 * 10^4

  • -1000 <= nums[i] <= 1000

  • -10^7 <= k <= 10^7

代码实现

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> mp;
        int sum=0,ans=0;
        mp[0]=1;
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
            if(sum==k||mp[sum-k]>0){
                ans+=mp[sum-k];
            }
            mp[sum]++;
        }
        return ans;
    }
};

返回目录