leetcode 930. Binary Subarrays With Sum 和相同的二元子数组

Problem: 930. Binary Subarrays With Sum 和相同的二元子数组

前缀和，哈希表记录每个和所在的索引i，对goal==0分开讨论的，使用前缀和- goal，拿到s = prefixSum[i+1] - goal;，数可能的子数组个数，并累加

Code

class Solution { public: int numSubarraysWithSum(vector<int>& nums, int goal) { vector<int> prefixSum = {0}; int n = nums.size(), s = 0; unordered_map<int, vector<int>> ump; ump[0] = {-1}; for(int i = 0; i < n; i++) { s += nums[i]; prefixSum.push_back(s); ump[s].push_back(i); } int ans = 0, l, r; for(int i = 0; i < n; i++) { s = prefixSum[i+1] - goal; if(ump.count(s) != 0) { if(goal==0) { ans += i - ump[s][0]; } else { r = l = ump[s].back(); while(l >= 0 && nums[l]==0) l--; ans += r - l + 1; } } } return ans; } };