自学内容网 自学内容网

【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 < = n u m s . l e n g t h < = 2 ∗ 1 0 4 1 <= nums.length <= 2 * 10^4 1<=nums.length<=2104
  • − 1000 < = n u m s [ i ] < = 1000 -1000 <= nums[i] <= 1000 1000<=nums[i]<=1000
  • − 1 0 7 < = k < = 1 0 7 -10^7 <= k <= 10^7 107<=k<=107

七【解题思路】

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

八【时空频度】

  • 时间复杂度: O ( n ) O(n) O(n) n n n为传入的数组的长度
  • 空间复杂度: O ( n ) O(n) O(n) n 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;
    }
}
  1. 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
  1. 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)!