Leetcode_hot100_560.和为k的子数组

题目要求

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

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

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

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

前缀和

  • 前缀和是指数组中从第一个元素到当前元素的和。对于数组 nums，前缀和数组 prefixSum 定义如下：
    • prefixSum[i] = nums[0] + nums[1] + … + nums[i-1]，其中 i 从 0 开始。
  • 假设prefixSum[i] 表示前 i 个元素的和，prefixSum[j] 表示前 j 个元素的和，那么子数组 nums[i…j-1] 的和可以表示为 prefixSum[j] - prefixSum[i]。
  • 因此，如果我们想找到和为 k 的子数组，我们需要满足 prefixSum[j] - prefixSum[i] = k，即 prefixSum[j] = prefixSum[i] + k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int subarraySum(int[] nums, int k) {
        // map的key是前缀和，value是该前缀和出现的次数
        Map<Integer, Integer> map = new HashMap<>();

        int sum = 0;
        int ans = 0;

        map.put(0,1);

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                ans += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}
  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。返回值不计入。