[LeetCode] 1248、 統計「優美子數組」

題目描述

給你一個整數數組

nums

和一個整數

k

。如果某個 連續 子數組中恰好有

k

個奇數數字，我們就認為這個子數組是「優美子數組」。請傳回這個數組中「優美子數組」的數目。

輸入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
輸出：16
           

解題思路

自己的第一反應是用“滑動視窗”的解法，但是沒想清楚怎麼弄，還是欠火候啊。。。

• 滑動視窗（ O ( n ) + O ( 1 ) O(n) + O(1) O(n)+O(1)，推薦！）：
  • 不斷右移

    right

    指針來擴大滑動視窗，使其包含

    k

    個奇數；
  • 若目前滑動視窗包含了

    k

    個奇數，則如下「計算目前視窗的優美子數組個數」：
    • 統計第

      1

      個奇數左邊的偶數個數

      leftEvenCnt

      。 這

      leftEvenCnt

      個偶數都可以作為「優美子數組」的起點，是以起點的選擇有

      leftEvenCnt + 1

      種（因為可以一個偶數都不取，是以别忘了 +1 喔）。
    • 統計第

      k

      個奇數右邊的偶數個數

      rightEvenCnt

      。 這

      rightEvenCnt

      個偶數都可以作為「優美子數組」的終點，是以終點的選擇有

      rightEvenCnt + 1

      種（因為可以一個偶數都不取，是以别忘了 +1 喔）。
    • 是以「優美子數組」左右起點的選擇組合數為

      (leftEvenCnt + 1) * (rightEvenCnt + 1)

      。
• 字首和（ O ( n ) + O ( n ) O(n) + O(n) O(n)+O(n)，有點不好了解，看看就好）：
  • 計算字首和數組

    arr

    ：周遊原數組，每周遊一個元素，計算目前的字首和（即到目前元素為止，數組中有多少個奇數）；
  • 對上述字首和數組，雙重循環統計

    arr[j] - arr[i] == k

    的個數，這樣做是 O(N^2)O(N2) 的（這裡會逾時哦）。
  • 優化：是以，我們可以像「1. 兩數之和」那樣使用

    HashMap

    優化到 O(N)O(N)，鍵是「字首和」，值是「字首和的個數」（下面代碼中具體使用的是

    int[] prefixCnt

    數組，下标是「字首和」，值是「字首和的個數」），是以我們可以周遊原數組，每周遊到一個元素，計算目前的字首和

    sum

    ，就在

    res

    中累加上字首和為

    sum - k

    的個數。

參考代碼

滑動視窗

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int left = 0, right = 0, oddCnt = 0, res = 0;
        while (right < nums.length) {
            // 右指針先走，每遇到一個奇數則 oddCnt++。
            if ((nums[right++] & 1) == 1) {
                oddCnt++;
            }

            //  若目前滑動視窗 [left, right) 中有 k 個奇數了，進入此分支統計目前滑動視窗中的優美子數組個數。
            if (oddCnt == k) {
                // 先将滑動視窗的右邊界向右拓展，直到遇到下一個奇數（或出界）
                // rightEvenCnt 即為第 k 個奇數右邊的偶數的個數
                int tmp = right;
                while (right < nums.length && (nums[right] & 1) == 0) {
                    right++;
                }
                int rightEvenCnt = right - tmp;
                // leftEvenCnt 即為第 1 個奇數左邊的偶數的個數
                int leftEvenCnt = 0;
                while ((nums[left] & 1) == 0) {
                    leftEvenCnt++;
                    left++;
                }
                // 第 1 個奇數左邊的 leftEvenCnt 個偶數都可以作為優美子數組的起點
                // (因為第1個奇數左邊可以1個偶數都不取，是以起點的選擇有 leftEvenCnt + 1 種）
                // 第 k 個奇數右邊的 rightEvenCnt 個偶數都可以作為優美子數組的終點
                // (因為第k個奇數右邊可以1個偶數都不取，是以終點的選擇有 rightEvenCnt + 1 種）
                // 是以該滑動視窗中，優美子數組左右起點的選擇組合數為 (leftEvenCnt + 1) * (rightEvenCnt + 1)
                res += (leftEvenCnt + 1) * (rightEvenCnt + 1);

                // 此時 left 指向的是第 1 個奇數，因為該區間已經統計完了，是以 left 右移一位，oddCnt--
                left++;
                oddCnt--;
            }

        }

        return res;
    }
}
           

字首和

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        // 數組 prefixCnt 的下标是字首和（即目前奇數的個數），值是字首和的個數。
        int[] prefixCnt = new int[nums.length + 1];
        prefixCnt[0] = 1;
        // 周遊原數組，計算目前的字首和，統計到 prefixCnt 數組中，
        // 并且在 res 中累加上與目前字首和內插補點為 k 的字首和的個數。
        int res = 0, sum = 0;
        for (int num: nums) {
            sum += num & 1;
            prefixCnt[sum]++;
            if (sum >= k) {
                res += prefixCnt[sum - k];
            }       
        }
        return res;
    }
}