esc to dismiss

930. 和相同的二元子数组

题目

给你一个二元数组 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

解题思路

这道题可以用 滑动窗口前缀和 + 哈希表 的算法来接。

滑动窗口容易理解,但代码量较多些;前缀和的代码比较简洁:

func numSubarraysWithSum(nums []int, goal int) int {
    countMap := make(map[int]int)
    var sum, count int
    for _, n := range nums {
        countMap[sum]++
        sum += n
        count += countMap[sum-goal]
    }
    return count
}

经验教训

...

x