LeetCode 930. 和相同的二元子数组（哈希+前缀和）

示例：
输入：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(vector<int>& A, int S) {
    	int n = A.size(), sum = 0, i = 0, count = 0;
    	unordered_map<int,int> m;//sum, 有多少个
    	m[0] = 1;//等于0的有1个
    	for(i = 0; i < n; i++) 
    	{
    		sum += A[i];//前缀和
    		if(m.find(sum-S) != m.end())
    			count += m[sum-S];
                //前缀和减去S后的前缀和存在，中间段就是和为S的
    		m[sum]++;
    	}
    	return count;
    }
};