930. 和相同的二元子数组 Medium

给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。

子数组 是数组的一段连续部分。

示例 1:
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

示例 2:
输入：nums = [0,0,0,0,0], goal = 0
输出：15

解题思路

输入：一个包含 0 和 1 的数组，一个整数 goal

输出：返回有多少个和为 goal 的非空子数组

本题属于哈希 + 前缀和问题。

我们可以使用 前缀和 的技巧，在遍历数组的过程中，记录“从起点累加到当前位置”的和。同时，用一个哈希表 freq 记录每个前缀和出现的次数。

核心思想：

• 对于每个位置的前缀和 pre_sum，我们判断是否有一个更早的前缀和 pre_sum - goal 出现过
• 如果存在，说明中间这段子数组的和正好为 goal
• 将所有满足条件的组合加起来，就是答案

代码实现

python

from collections import defaultdict

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        pre_sum = 0                # 当前的前缀和（从数组起点累加到当前位置）
        count = 0                 # 满足条件的子数组数量
        freq = defaultdict(int)   # 用来记录各个前缀和出现的次数
        freq[0] = 1               # 初始化：前缀和为 0 出现 1 次（表示空数组）

        for num in nums:
            pre_sum += num        # 更新当前前缀和

            # 如果 pre_sum - goal 在 freq 中出现过，
            # 说明存在某段子数组的和为 goal
            count += freq[pre_sum - goal]

            # 记录当前前缀和的出现次数
            freq[pre_sum] += 1

        return count              # 返回满足条件的子数组个数

javascript

const numSubarraysWithSum = function(nums, goal) {
    // 满足条件的子数组数量
    let count = 0;
    // 当前的前缀和（从数组起点累加到当前位置）
    let preSum = 0;
    // 用来记录各个前缀和出现的次数
    // 初始化：前缀和为 0 出现 1 次（表示空数组）
    const freq = {0: 1};

    for (let num of nums) {
        // 更新当前前缀和
        preSum += num;

        // 如果 pre_sum - goal 在 freq 中出现过
        // 说明存在某段子数组的和为 goal
        count += (freq[preSum - goal] || 0)

        // 记录当前前缀和的出现次数
        freq[preSum] = (freq[preSum] || 0) + 1
    }

    // 返回满足条件的子数组个数
    return count;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

930 国际版

930 中文版