【算法笔记】力扣热题100（LeetCode hot-100）560. 和为 K 的子数组

力扣热题100（LeetCode hot-100）之 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 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

题解

这个问题，一般怎么解？

思路：

使用 前缀和 和 哈希表 的方法。

1. 定义一个哈希表 map，用于存储前缀和及其出现的次数。
2. 初始化前缀和 preSum 为 0，前缀和为 0 的个数为 1。
3. 遍历数组，计算当前的前缀和 preSum。
4. 如果 map 中存在 preSum - k，说明存在一个子数组的和为 k，更新计数器 count。
5. 更新哈希表中前缀和的个数

答案

class Solution {
    public int subarraySum(int[] nums, int k) {
        final var map = new HashMap<Integer, Integer>();
        // 初始化，前缀和为0的个数为1
        map.put(0, 1);
        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;
            if (map.containsKey(preSum - k)) { // 如果存在前缀和为preSum - k的子数组，那么这个子数组到当前位置的和为k
                count += map.get(preSum - k);
            }
            // 更新前缀和为preSum的子数组个数
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}

原文地址：https://blog.csdn.net/weixin_47157828/article/details/145291308

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