1524.png

求和為奇數的子數組數組，如果直接暴力枚舉顯示不可取的，數據范圍比較大。

涉及到的數組和的問題，通常第一想法就是考慮能不能用前綴和去處理一下。

對應到這題中，正好可以用前綴和處理，在處理每個位置的前綴和時，我們可以動態(tài)的維護一種長度為2的數組，這個數組用于統(tǒng)計 【截止到當前位置】和為奇數或者偶數的數量

數組： arr = [1, 3, 5]
前綴和為： sum = [0 , 1, 4, 9]
統(tǒng)計數組結果分別為： [1, 0] [1, 1] [2, 1] [2, 2]

這個統(tǒng)計數組有何用？
用于實現不同的組合的累加

以統(tǒng)計數組的第三個狀態(tài)：即前綴和為4時，對應的統(tǒng)計狀態(tài)[2, 1]，表示目前位置有2個和為偶數，一個和為奇數。
接下來利用統(tǒng)計數組的中的奇或偶的個數進行不同的【組合】，遍歷到 前綴和4時，4是偶數，要想變成奇數，那么就必須與奇數相加才可以，因為 4 可以和【任意一個】奇數相組合。

class Solution {
    int mod = (int)1e9 + 7;
    public int numOfSubarrays(int[] arr) {
        int[] cnt = new int[] {1, 0};
        int n = arr.length;
        long r = 0;
        for(int i = 0, sum = 0; i < n; i++) {
            ++cnt[sum ^= arr[i] & 1];
            r += cnt[sum ^ 1];
        }
        return (int) (r % mod);
    }
}