Question

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

题目描述

给定一个正整数数组和一个整数 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/problems/subarray-sum-equals-k/

解法

方法一：哈希表 + 前缀和

由于数组中既有正数又有负数，无法使用双指针。我们可以使用哈希表记录每个前缀和出现的次数，从而在 $O(1)$ 的时间内得到以当前位置为右端点的子数组中和为 $k$ 的子数组个数。

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

class Solution:
  def subarraySum(self, nums: List[int], k: int) -> int:
    cnt = Counter({0: 1})
    ans = s = 0
    for x in nums:
      s += x
      ans += cnt[s - k]
      cnt[s] += 1
    return ans

class Solution {
  public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    int ans = 0, s = 0;
    for (int x : nums) {
      s += x;
      ans += cnt.getOrDefault(s - k, 0);
      cnt.merge(s, 1, Integer::sum);
    }
    return ans;
  }
}

class Solution {
public:
  int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    cnt[0] = 1;
    int ans = 0, s = 0;
    for (int x : nums) {
      s += x;
      ans += cnt[s - k];
      cnt[s]++;
    }
    return ans;
  }
};

func subarraySum(nums []int, k int) (ans int) {
  cnt := map[int]int{0: 1}
  s := 0
  for _, x := range nums {
    s += x
    ans += cnt[s-k]
    cnt[s]++
  }
  return
}

function subarraySum(nums: number[], k: number): number {
  const cnt: Map<number, number> = new Map();
  cnt.set(0, 1);
  let ans = 0;
  let s = 0;
  for (const x of nums) {
    s += x;
    ans += cnt.get(s - k) ?? 0;
    cnt.set(s, (cnt.get(s) ?? 0) + 1);
  }
  return ans;
}