LeetCode 1248

https://leetcode-cn.com/problems/count-number-of-nice-subarrays/

这个题一开始暴力双指针，T了，遂放弃。

后来看了下提示，在 nums = [2,2,2,1,2,2,1,2,2,2], k = 2 这个测试用例中得到了灵感，因为这个的子数组个数为4+4+4+4。将数组内的奇数的位置提取出来后为[3,6]，仔细一看(3-0+1)*(10-6)不是刚好等于16吗，所以就开始这种想法。

但是在实现的过程中，我发现我想的还是不够深入，比如说在第一个测试用例中就会有不同的结果，我当时也没认真的细想，知道最后看了解析才明白我的想法错在哪里。

https://leetcode-cn.com/problems/count-number-of-nice-subarrays/solution/suo-yin-shu-zu-jie-fa-by-geguanting/

这个是他的想法，跟我的思路很像，但是处理的细节方面他比我强得多。

首先，我的想法中的3-0+1这个地方应该变成这个奇数与前一个奇数出现的差，而不是与0的关系。

其次，右手边的10-6，在算法中应该是从当前奇数出发的第k个奇数出现的位置与第k-1个奇数之差。

他的想法巧妙地在list中添加-1和nums.length来避免了多余的计算。。。。。

题目做多了，想法还是有的，但是实现还是比较难想得到，做的还是不够细致啊。

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k <1){
            return 0;
        }
        ArrayList<Integer> index = new ArrayList<>();
        int res = 0;
        index.add(-1);
        for(int i = 0;i < nums.length;i++) {
            if (nums[i] % 2 == 1) {
                index.add(i);
            }
        }
        index.add(nums.length);
        for(int i = 1; i < index.size()-k;i++){
            int left = index.get(i) - index.get(i-1);
            int right = index.get(i+k) - index.get(i+k-1);
            res += left*right;
        }
        return res;
    }
}