560. 和为 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

出处：LeetCode

解法一：暴力法

思路

我们可以使用暴力法来解决这个问题。我们可以遍历数组 nums，对于每个元素 nums[i]，我们可以计算以 i 结尾的子数组的和 sum，然后我们可以统计和为 k 的子数组的个数。

代码

function subarraySum(nums: number[], k: number): number {
  let count = 0;

  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j >= 0; j--) {
      sum += nums[j];
      if (sum === k) {
        count++;
      }
    }
  }

  return count;
}

复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

解法二：前缀和 + 哈希表

思路

我们可以使用前缀和来解决这个问题。首先，我们需要计算数组 nums 的前缀和数组 preSum，其中 preSum[i] 表示数组 nums 中 [0, i] 区间内元素的和。接着，我们可以使用一个哈希表 map 来记录前缀和出现的次数。我们可以遍历数组 nums，在遍历的过程中，我们可以计算以 i 结尾的子数组的和 sum，然后我们可以通过 sum - k 来得到以 i 结尾的子数组和为 k 的子数组的个数。

代码

function subarraySum(nums: number[], k: number): number {
  const map = new Map<number, number>();
  map.set(0, 1);
  let preSum = 0;
  let count = 0;

  for (let i = 0; i < nums.length; i++) {
    preSum += nums[i];
    if (map.has(preSum - k)) {
      count += map.get(preSum - k)!;
    }
    map.set(preSum, (map.get(preSum) || 0) + 1);
  }

  return count;
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$