Medium

题目描述

给定一个二进制数组 nums 和一个整数 goal，返回和为 goal 的非空子数组的数量。

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

示例 1:

输入: nums = [1,0,1,0,1], goal = 2
输出: 4
解释: 4 个子数组如下所示（用粗体下划线表示）：
[1,0,1,0,1]
[1,0,1,0,1]  
[1,0,1,0,1]
[1,0,1,0,1]

示例 2:

输入: nums = [0,0,0,0,0], goal = 0
输出: 15

提示:

  • 1 <= nums.length <= 3 * 10^4
  • nums[i] 只能是 0 或 1
  • 0 <= goal <= nums.length

解题思路

这道题要求统计和为目标值的子数组个数，有三种主要解法：

解法一：前缀和 + 哈希表 核心思想是利用前缀和的性质。如果前缀和 prefixSum[j] - prefixSum[i] = goal，那么子数组 nums[i+1...j] 的和就是 goal。我们遍历数组，维护前缀和，并用哈希表记录每个前缀和出现的次数。对于当前位置的前缀和 sum，我们查找 sum - goal 在哈希表中的出现次数，这就是以当前位置为结尾且和为 goal 的子数组个数。

解法二：滑动窗口 由于数组只包含 0 和 1，我们可以用滑动窗口技巧。关键观察是：如果存在和为 goal 的子数组，那么在满足条件的最短子数组基础上，可以通过在左侧添加连续的 0 来得到更多满足条件的子数组。

解法三：数学转换 将问题转换为"和小于等于 goal 的子数组个数" 减去 “和小于等于 goal-1 的子数组个数”。这样可以用单调滑动窗口来解决。

推荐使用前缀和 + 哈希表的解法，思路清晰且容易理解。

代码实现

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        unordered_map<int, int> prefixCount;
        prefixCount[0] = 1; // 前缀和为0的情况
        int sum = 0, result = 0;
        
        for (int num : nums) {
            sum += num;
            if (prefixCount.find(sum - goal) != prefixCount.end()) {
                result += prefixCount[sum - goal];
            }
            prefixCount[sum]++;
        }
        
        return result;
    }
};

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        prefix_count = {0: 1}  # 前缀和为0的情况
        current_sum = 0
        result = 0
        
        for num in nums:
            current_sum += num
            if current_sum - goal in prefix_count:
                result += prefix_count[current_sum - goal]
            prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1
        
        return result

public class Solution {
    public int NumSubarraysWithSum(int[] nums, int goal) {
        Dictionary<int, int> prefixCount = new Dictionary<int, int>();
        prefixCount[0] = 1; // 前缀和为0的情况
        int sum = 0, result = 0;
        
        foreach (int num in nums) {
            sum += num;
            if (prefixCount.ContainsKey(sum - goal)) {
                result += prefixCount[sum - goal];
            }
            if (prefixCount.ContainsKey(sum)) {
                prefixCount[sum]++;
            } else {
                prefixCount[sum] = 1;
            }
        }
        
        return result;
    }
}

var numSubarraysWithSum = function(nums, goal) {
    const prefixCount = new Map();
    prefixCount.set(0, 1); // 前缀和为0的情况
    let sum = 0, result = 0;
    
    for (const num of nums) {
        sum += num;
        if (prefixCount.has(sum - goal)) {
            result += prefixCount.get(sum - goal);
        }
        prefixCount.set(sum, (prefixCount.get(sum) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型前缀和+哈希表解法
时间复杂度O(n)
空间复杂度O(n)

其中 n 为数组长度。时间复杂度为 O(n) 是因为需要遍历一次数组，每次哈希表操作的平均时间复杂度为 O(1)。空间复杂度为 O(n) 是因为在最坏情况下，哈希表需要存储 n+1 个不同的前缀和。

相关题目