0560. 和为 K 的子数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀和 + 哈希表

1. 📝 题目描述

• leetcode

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

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

---

示例 1：

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

---

示例 2：

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

---

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

2. 🎯 s.1 - 前缀和 + 哈希表

c

#define MAX_SIZE 20001
typedef struct Entry { int key; int val; struct Entry* next; } Entry;

int subarraySum(int* nums, int numsSize, int k) {
    Entry* table[MAX_SIZE];
    memset(table, 0, sizeof(table));
    int count = 0, prefixSum = 0;

    // insert (0, 1)
    int h0 = ((0 % MAX_SIZE) + MAX_SIZE) % MAX_SIZE;
    Entry* e0 = (Entry*)malloc(sizeof(Entry));
    e0->key = 0; e0->val = 1; e0->next = table[h0];
    table[h0] = e0;

    for (int i = 0; i < numsSize; i++) {
        prefixSum += nums[i];
        int target = prefixSum - k;
        int h = ((target % MAX_SIZE) + MAX_SIZE) % MAX_SIZE;
        for (Entry* e = table[h]; e; e = e->next) {
            if (e->key == target) { count += e->val; break; }
        }
        h = ((prefixSum % MAX_SIZE) + MAX_SIZE) % MAX_SIZE;
        Entry* found = NULL;
        for (Entry* e = table[h]; e; e = e->next) {
            if (e->key == prefixSum) { found = e; break; }
        }
        if (found) found->val++;
        else {
            Entry* ne = (Entry*)malloc(sizeof(Entry));
            ne->key = prefixSum; ne->val = 1; ne->next = table[h];
            table[h] = ne;
        }
    }
    return count;
}

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  const map = new Map([[0, 1]])
  let prefixSum = 0,
    count = 0
  for (const num of nums) {
    prefixSum += num
    count += map.get(prefixSum - k) || 0
    map.set(prefixSum, (map.get(prefixSum) || 0) + 1)
  }
  return count
}

py

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        cnt[0] = 1
        prefix_sum = count = 0
        for num in nums:
            prefix_sum += num
            count += cnt[prefix_sum - k]
            cnt[prefix_sum] += 1
        return count

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(n)$

算法思路：

• 维护前缀和及其出现次数的哈希表
• 遍历时查找 prefixSum - k 是否在哈希表中，若存在则累加其出现次数