【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<=nums.length<=2\ast 10^4$
• $-1000<=nums[i]<=1000$
• $-10^7<=k<=10^7$

七【解题思路】

• 使用前缀和+哈希表解决该问题
• 前缀和都很清楚了，那么如何与哈希表结合在一起呢？
  • 在本题中，我们使用哈希表记录当前前缀和的出现次数
  • 在每次得到新的前缀和时，就去哈希表中找“当前前缀和 - k”的值对应的次数，“当前前缀和 - k”对应的就是“之前前缀和”
  • 这样，我们就找到满足“之前前缀和 + 当前前缀和 = k”的子数组，即和为 K 的子数组
• 通过这种方法，可以有效地降低时间复杂度
• 最后返回结果即可
• 具体细节可以参考下面的代码

八【时空频度】

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

九【代码实现】

1. 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;
    }
}

2. 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

3. 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;
    }
};

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版
   

原文地址：https://blog.csdn.net/IronmanJay/article/details/143077096

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！