560.和为 K 的子数组

【LetMeFly】560.和为 K 的子数组

力扣题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/

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

 

示例 1：

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

示例 2：

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

 

提示：

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

方法一：哈希 + 前缀和

使用cnt记录遍历过程中的所有元素的和，使用哈希表统计当前cnt出现过的次数。

既然当前的前缀和为cnt，那么假如前面存在为$cnt - k$的前缀和的话，这两个位置之间的子数组的和就为$k$

因此，我们直接将$cnt - k$在哈希表中出现的次数累加到答案中即可

动画演示可见官解方法二的动图

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(len(nums))$

AC代码

C++

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

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans = 0
        ma = defaultdict(int)
        ma[0] = 1
        cnt = 0
        for n in nums:
            cnt += n
            if cnt - k in ma:
                ans += ma[cnt - k]
            ma[cnt] += 1
        return ans

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/129547610