+++
date = “2022-02-11T08:55:19+08:00”
title = “LeetCode每日练习：剑指 Offer II 010. 和为 k 的子数组”
categories = [“大四LeetCode算法刷题”]
tags = [“LeetCode”,”C++”,”前缀和”]
toc = true
author = “qk”
author_homepage = “https://qkgoalkeeper.github.io/“

+++

一.剑指 Offer II 010. 和为 k 的子数组

1.题干及思路

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

示例 1 :

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

示例 2 :

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

提示:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

注意：本题与主站 560 题相同： https://leetcode-cn.com/problems/subarray-sum-equals-k/

要点：前缀和

思路：如果全是正数那么就可以用滑动窗口，但是这里有负数所以用哈希表加前缀和来做，哈希表的key为当前前缀和sum，value为当前前缀和sum出现次数每次加一，遍历时每次给answer添加hash[sum-k]（如果有的话），注意一开始要添加hash[0] = 1

2.C++实现

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