问题:在由若干 01 组成的数组 A 中,有多少个和为 S 的非空子数组。

示例:

**输入:**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]

**思路:**这道题类似一个特殊的动态规划,维护一个到当前索引为止的数组元素和curSum以及一张哈希表来记录累积和过程中所有数值出现的次数,比如map.get(2)返回的就是当前索引为止,和为2的连续子数组的个数。那么如果curSum为5,那么map.get(curSum - S)返回的就是当前和为S的子数组个数。

代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int numSubarraysWithSum(int[] A, int S) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int curSum = 0;
        int count = 0;
        for(int num : A){
            curSum += num;
            if(map.containsKey(curSum - S)){
                count += map.get(curSum - S);
            }
            map.put(curSum, map.getOrDefault(curSum, 0) + 1);
        }
        return count;
    }
}