# 1524. Number of Sub-arrays With Odd Sum
###### tags: `Leetcode` `Medium` `HashMap` `Prefix Sum`
Link: https://leetcode.com/problems/number-of-sub-arrays-with-odd-sum/
## 思路
说是用到hashmap实际上并没有
之所以放在hashmap tag里面是因为和别的hashmap+prefixsum的题很像
随着遍历，记录prefixsum，如果prefixsum是奇数，那么包含这个数的和为奇数的subarray = 前面偶数和的数目，vice versa
所以不需要用map，只需要一个size为2的array就可以
## Code
java

class Solution {
    public int numOfSubarrays(int[] arr) {
        int mod = 1000000007;
        int sum = 0;
        int[] cnt = new int[2];
        cnt[0] = 1;
        int ans = 0;
        for(int i=0; i<arr.length; i++){
            sum += arr[i];
            ans = (cnt[1-sum%2]%mod + ans%mod)%mod;
            cnt[sum%2]++;
        }
        return ans;
    }
}

c++

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int mod = 1000000007;
        long cnt[2] = {};
        cnt[0] = 1;
        long ans = 0;
        long sum = 0;
        for(int num:arr){
            sum+=num;
            ans = (ans+cnt[1-sum%2])%mod;
            cnt[sum%2]++;
        }
        return (int)ans;
    }
};