import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _1248 {
    static class Solution1 {
        public int numberOfSubarrays(int[] nums, int k) {
            //滑动窗口..
            int even = 0;
            //统计某个奇数前后存在的偶数数量
            int[] count = new int[nums.length];
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] % 2 == 0) {
                    even++;
                } else {
                    list.add(i);//只加索引
                    if (i > 0) {
                        count[i - 1] = even;
                        even = 0;
                    }
                }
            }
            even = 0;
            for (int j = nums.length - 1; j >= 0; j--) {
                if (nums[j] % 2 == 0) {
                    even++;
                } else {
                    if (j < nums.length - 1) {
                        count[j + 1] = even;
                        even = 0;
                    }
                }
            }
            int i = 0;
            int j = k - 1;
            int res = 0;
            while (j < list.size()) {
                int l = list.get(i) > 0 ? 1 + count[list.get(i) - 1] : 1;
                int r = list.get(j) < nums.length - 1 ? count[list.get(j) + 1] + 1 : 1;
                res += l * r;
                i++;
                j++;
            }
            return res;
        }
    }

    static class Solution2 {
        public int numberOfSubarrays(int[] nums, int k) {
            //别人的滑动窗口
            // 对于[x...y] xy都为奇数的情况下，以[x...y]为中心，两侧的连续偶数数量分别为 ex,ey, 能组成的
            //子数组和为k的数量为(ex+1)*(ey+1);这里只不过使count为ex + 1,然后累加 ey+1次
            int i = 0;
            int count = 0;
            int res = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] % 2 == 1) {
                    k -= nums[j] % 2;
                    count = 0;
                }
                while (k == 0) {
                    k += nums[i++] % 2;
                    count++;
                }
                res += count;
            }
            return res;
        }
    }

    static class Solution3 {
        public int numberOfSubarrays(int[] nums, int k) {
            int[] prefixSum = new int[nums.length];
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i] % 2;
                prefixSum[i] = sum;
            }
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                res += map.getOrDefault(prefixSum[i] - k, 0);
                map.put(prefixSum[i], map.getOrDefault(prefixSum[i], 0) + 1);
            }
            return res;
        }
    }
}