LeetCode——统计[优美子数组]

NO.1248 统计[优美子数组] 中等

思路一：和为K的子数组 NO.560和为K的子数组是统计子数组中的元素和，本题是统计子数组中的奇数个数。那么就将本题的数组进行转换，偶数不需要统计记为0，奇数需要统计记为1。然后就可以进行NO.560和为K的子数组一样的处理。

public int numberOfSubarrays(int[] nums, int k) {
    //奇数为1，偶数为0
    for (int i = 0; i < nums.length; i++) {
        nums[i] = (nums[i] & 1) == 1 ? 1 : 0;
    }
    //和为K的子数组
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0, count = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum - k)) {
            count += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

时间复杂度：O(n) 两次遍历。

空间：O(n)

思路二：滑动窗口

1. 先找到包含K个奇数的最小子数组(窗口)，这个子数组的左右边界一定都是奇数元素。
2. 然后分别向左、向右扩展窗口，直至走到边界或下一个元素是奇数为止。
3. (向左扩展次数+不扩展算1次)*(向右扩展次数+不扩展算1次)=包含当前K个奇数的子数组的个数

所以重点就是关注奇数元素的位置，顺便需要考虑上边界值的问题。

综上所述，可以将奇数的下标保存至一个数组，这个数组的首尾记为参数数组的边界即-1、length。

有了奇数元素的索引数组之后就可以轻而易举的按照上述思路计算出子数组的个数了。

例如，输入[0,1,1,0,1,0,0,1,0]且K=3，遍历得到所有奇数的索引数组odds[-1,1,2,4,7,9]包含边界值。

按照上述三步，找到包含K个奇数的窗口区间[1,4]，然后根据向左扩展向右扩展=(odds[1]-odds[0])\(odds[4]-odds[3])=6；

另一个包含K个奇数的窗口期间区间[2,7]，然后还是那个公式(odds[2]-odds[1])*(odds[5]-odds[4])=2；

相加得到8。

public int numberOfSubarrays(int[] nums, int k) {
    int oddsNum = 0, count = 0;
    //记录奇数元素索引
    int[] odds = new int[nums.length + 2];
    for (int i = 0; i < nums.length; i++) {
        if ((nums[i] & 1) == 1) {
            odds[++oddsNum] = i;
        }
    }
    //左右边界
    odds[0] = -1;
    odds[oddsNum + 1] = nums.length;
    //包含K个奇数的窗口区间[odds[i],odds[i+k]]
    for (int i = 1; i + k < oddsNum + 2; i++) {
        count += (odds[i] - odds[i - 1]) * (odds[i + k] - odds[i + k - 1]);
    }
    return count;
}

时间复杂度：O(n) 最坏情况也是两次遍历。

空间：O(n)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github