Q930 和相同的二元子数组

佚名 7年前 (2019-05-06) 随笔 1948人围观抢沙发百度已收录

在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组。

示例：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入：A = [1,0,1,0,1], S = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

提示：

A.length <= 30000
0 <= S <= A.length
A[i] 为 0 或 1

class Solution {
    public int numSubarraysWithSum(int[] A, int S) {
        int sum = 0;
        int result = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        for (int i : A) {
            sum += i;
            result += map.getOrDefault(sum - S, 0);
            int t = map.getOrDefault(sum, 0) + 1;
            map.put(sum, t);
        }

        return result;
    }
}