LeetCode560-和为K的子数组

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/subarray-sum-equals-k/

中文链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/

题目详述

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

1
2
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

题目详解

  • 思路：对数组求前缀和，这样连续子数组的和就可以用两个前缀和之差算出来。
  • 为了计算个数，用一个 Map 记录每个前缀和出现的次数。
  • 遍历数组，假设当前前缀和为 s，在 map 中查找前缀和为 s - k 的出现次数，加入到结果中。
  • 为了计算正确，map 在初始时要放入一个代表前缀和为 0 出现过 1 次的键值对。
  • 时间复杂度为 O(n)，空间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00560 {

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 初始时放入一个代表前缀和为 0 出现过 1 次的键值对
        map.put(0, 1);
        int res = 0;
        int s = 0;
        for (int num : nums) {
            s += num;
            res += map.getOrDefault(s - k, 0);
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        return res;
    }
}