LeetCode 560：和为 K 的子数组（前缀和+哈希表解法）

LeetCode 560：和为 K 的子数组（前缀和+哈希表解法）

引用

CSDN

1.

https://blog.csdn.net/IronmanJay/article/details/143077096

本文将详细讲解LeetCode第560题“和为 K 的子数组”的解题思路和代码实现。这是一道中等难度的题目，主要考察前缀和与哈希表的结合使用。通过本文的讲解，读者将能够掌握如何使用前缀和+哈希表的算法来解决此类问题。

一、题目类别

• 前缀和

二、题目难度

• 中等

三、题目编号

• 560.和为 K 的子数组

四、题目描述

• 给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。
• 子数组是数组中元素的连续非空序列。

五、题目示例

示例 1：

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

示例 2：

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

六、题目提示

• $1 \le nums.length \le 2 \times 10^4$
• $-1000 \le nums[i] \le 1000$
• $-10^7 \le k \le 10^7$

七、解题思路

使用前缀和+哈希表解决该问题

在本题中，我们使用哈希表记录当前前缀和的出现次数

在每次得到新的前缀和时，就去哈希表中找“当前前缀和 - k”的值对应的次数，“当前前缀和 - k”对应的就是“之前前缀和”

这样，我们就找到满足“之前前缀和 + 当前前缀和 = k”的子数组，即和为 K 的子数组

通过这种方法，可以有效地降低时间复杂度

最后返回结果即可

具体细节可以参考下面的代码

八、时空频度

• 时间复杂度：$O(n)$，n 为传入的数组的长度
• 空间复杂度：$O(n)$，n 为传入的数组的长度

九、代码实现

Java语言版

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 初始化哈希表，前缀和为0的情况为1次
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        // 记录满足条件的子数组个数
        int count = 0;
        // 初始化前缀和
        int prefixSum = 0;
        for (int num : nums) {
            // 计算当前的前缀和
            prefixSum += num;
            // 检查是否存在 prefix_sum - k 的前缀和
            if (hashMap.containsKey(prefixSum - k)) {
                // 加上满足条件的前缀和个数
                count += hashMap.get(prefixSum - k);
            }
            // 更新哈希表中的当前前缀和出现次数
            hashMap.put(prefixSum, hashMap.getOrDefault(prefixSum, 0) + 1);
        }
        return count;
    }
}

Python语言版

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 初始化哈希表，前缀和为0的情况为1次
        hash_map = {0 : 1}
        # 记录满足条件的子数组个数
        count = 0
        # 初始化前缀和
        prefix_sum = 0
        for num in nums:
            # 计算当前的前缀和
            prefix_sum += num
            # 检查是否存在 prefix_sum - k 的前缀和
            if prefix_sum - k in hash_map:
                # 加上满足条件的前缀和个数
                count += hash_map[prefix_sum - k]
            # 更新哈希表中的当前前缀和出现次数
            hash_map[prefix_sum] = hash_map.get(prefix_sum, 0) + 1
        return count

C++语言版

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 初始化哈希表，前缀和为0的情况为1次
        unordered_map<int, int> hashMap;
        hashMap[0] = 1;
        // 记录满足条件的子数组个数
        int count = 0;
        // 初始化前缀和
        int prefixSum = 0;
        for (int num : nums) {
            // 计算当前的前缀和
            prefixSum += num;
            // 检查是否存在 prefix_sum - k 的前缀和
            if (hashMap.find(prefixSum - k) != hashMap.end()) {
                // 加上满足条件的前缀和个数
                count += hashMap[prefixSum - k];
            }
            // 更新哈希表中的当前前缀和出现次数
            hashMap[prefixSum]++;
        }
        return count;
    }
};

十、提交结果

Java语言版

Python语言版

C++语言版