1248. 統計「優美子數組」（java）

1248. 統計「優美子數組」

題目描述：

給你一個整數數組 nums 和一個整數 k。

如果某個 連續 子數組中恰好有 k 個奇數數字，我們就認為這個子數組是「優美子數組」。

請傳回這個數組中「優美子數組」的數目。

示例 1：

輸入：nums = [1,1,2,1,1], k = 3

輸出：2

解釋：包含 3 個奇數的子數組是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2：

輸入：nums = [2,4,6], k = 1

輸出：0

解釋：數列中不包含任何奇數，是以不存在優美子數組。

示例 3：

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

輸出：16

提示：

1 <= nums.length <= 50000

1 <= nums[i] <= 10^5

1 <= k <= nums.length

解法一：滑動視窗

• 步驟
  • 找出k個奇數的左右邊界
  • 找出首個奇數前面數字邊界及第k個奇數的下一個奇數邊界，計算個數
  • (leftEvenCnt + 1) * (rightEvenCnt + 1)
• 參數說明
  • left 、right為目前k個奇數的最小連續數組範圍
  • leftcnt、rightcnt為除開k個奇數與前後一個奇數的個數（可以進行組合成優美子數組）

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int left=0,right=0,oddCnt=0,res=0;
        while(right<nums.length){
            //或者用nums[right++]&1
            //右指針先走
            if((nums[right++]%2)==1){
                oddCnt++;
            }
            //有k個奇數了
            if(oddCnt==k){
                //開始計算到右邊界個數
                int temp=right;
                while(right<nums.length&&(nums[right]%2)==0) {
                    right++;
                }
                int rightcnt=right-temp;
                //計算到左邊界個數
                int leftcnt=0;
                while((nums[left]%2)==0){
                    left++;
                    leftcnt++;
                }
                //目前可組合的數組數
                res+=(rightcnt+1)*(leftcnt+1);
                //去掉目前數組的首個奇數
                left++;
                oddCnt--;
            }
        }
        return res;
    }
}
           

解法二：字首和

• 用一個數組prefixCnt存儲
  • 下标是[奇數和]，值是[奇數和的個數]
  • sum-k就是要累加的個數，如sum=2 k=2時 在藍色部分情況共4次，每次遇見該情況都計算字首和，即黃色數3+1次，

  • 

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int[] prefixCont = new int[nums.length+1];
        prefixCont[0]++;
        int sum=0,res=0;
        for(int num:nums){
            sum+=num%2;
            prefixCont[sum]++;
            if(sum>=k){
                res+=prefixCont[sum-k];
            }
        }
        return res;
    }
}