LeetCode 560. 和为 K 的子数组

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 560. 和为 K 的子数组原题链接中等

作者：

wzc1995 , 2018-07-15 02:23:56 , 所有人可见 , 阅读 3959

33

13

题目描述

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

样例

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

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

限制

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

算法

(前缀和，哈希表) $O(n)$

对原数组求前缀和后，一个和为 k 的子数组即为一对前缀和的差值为 k 的位置。
遍历前缀和数组，用 unordered_map 哈希表记录每个前缀和出现的次数。特别地，初始时前缀和为 0 需要被额外记录一次。
遍历过程中，对于当前前缀和 tot，累加之前 tot - k 前缀和出现的次数。

时间复杂度

每个位置仅遍历一次，哈希表单次操作的时间复杂度为常数，故总时间复杂度为 $O(n)$。

空间复杂度

需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

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

21 评论

磨叽 2021-05-11 09:27

大佬们都水平太高，没有点到小白对这题的盲点：数的范围是有正负的，所以前缀和是可以有重复的，而不是递增的。

acwing_4007 2022-04-16 18:53

为什么hash[tot]++;在ans += hash[tot - k];这个后面呢

wzc1995 2022-04-16 21:44

避免 k==0 的情况

Jahdo_w 2023-10-11 10:55

Java代码

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