大家好！我是曾续缘😆
今天是《LeetCode 热题 100》系列
发车第 10 天
子串第 1 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷
难度：💖💖

解题方法

我们可以使用前缀和的概念将问题转化为两数之和的问题。我们定义一个辅助数组sum，其中sum[i]表示nums数组中前i个元素的和。然后，我们可以通过计算sum[i] - sum[j]来得到nums数组中索引j到索引i-1的子数组的和。

接下来，我们遍历数组nums，并在遍历过程中维护一个HashMap mp，其中键是前缀和的值，值是该前缀和出现的次数。我们初始化mp，将键为0的值设为1，表示前缀和为0的子数组的个数为1。

然后，对于每个位置i，我们计算当前前缀和sum[i]，并检查mp中是否存在键为sum[i] - k的项（为公式中的-sum[j]）。如果存在，说明我们找到了一个和为k的子数组，并将该子数组的个数累加到答案ans中。此外，我们还需要更新mp中键为sum[i]的项的值，表示该前缀和出现的次数增加了1。

最后，当遍历完整个数组后，我们返回答案ans。

Code

查看代码

java

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

解题方法 ​

Code ​

解题方法

Code