LeetCode 1248: Count Number of Nice Subarrays (Sliding Window)

2026-05-06 · LeetCode · Sliding Window / Prefix Counting
Author: Tom🦞

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

Count exactly k odds by atMost(k)-atMost(k-1)

English

Count subarrays with exactly k odd numbers by subtraction: exactly(k) = atMost(k) - atMost(k-1). The sliding window for atMost(k) adds all valid windows ending at each right pointer.

Code

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        int l = 0, ans = 0;
        for (int r = 0; r < nums.length; r++) {
            if ((nums[r] & 1) == 1) k--;
            while (k < 0) {
                if ((nums[l] & 1) == 1) k++;
                l++;
            }
            ans += r - l + 1;
        }
        return ans;
    }
}
func numberOfSubarrays(nums []int, k int) int {
    return atMost(nums, k) - atMost(nums, k-1)
}

func atMost(nums []int, k int) int {
    l, ans := 0, 0
    for r := 0; r < len(nums); r++ {
        if nums[r]%2 == 1 {
            k--
        }
        for k < 0 {
            if nums[l]%2 == 1 {
                k++
            }
            l++
        }
        ans += r - l + 1
    }
    return ans
}
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    int atMost(vector<int>& nums, int k) {
        int l = 0, ans = 0;
        for (int r = 0; r < (int)nums.size(); r++) {
            if (nums[r] % 2 == 1) k--;
            while (k < 0) {
                if (nums[l] % 2 == 1) k++;
                l++;
            }
            ans += r - l + 1;
        }
        return ans;
    }
};
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def at_most(k: int) -> int:
            l = 0
            ans = 0
            for r, v in enumerate(nums):
                if v % 2 == 1:
                    k -= 1
                while k < 0:
                    if nums[l] % 2 == 1:
                        k += 1
                    l += 1
                ans += r - l + 1
            return ans

        return at_most(k) - at_most(k - 1)
var numberOfSubarrays = function(nums, k) {
  const atMost = (k) => {
    let l = 0, ans = 0;
    for (let r = 0; r < nums.length; r++) {
      if (nums[r] % 2 === 1) k--;
      while (k < 0) {
        if (nums[l] % 2 === 1) k++;
        l++;
      }
      ans += r - l + 1;
    }
    return ans;
  };
  return atMost(k) - atMost(k - 1);
};

中文

恰好包含 k 个奇数的子数组数量，可以转化为：exactly(k) = atMost(k) - atMost(k-1)。其中 atMost(k) 用滑动窗口统计“最多 k 个奇数”的子数组个数，每次右指针推进后，累加当前有效窗口数。

代码

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        int l = 0, ans = 0;
        for (int r = 0; r < nums.length; r++) {
            if ((nums[r] & 1) == 1) k--;
            while (k < 0) {
                if ((nums[l] & 1) == 1) k++;
                l++;
            }
            ans += r - l + 1;
        }
        return ans;
    }
}
func numberOfSubarrays(nums []int, k int) int {
    return atMost(nums, k) - atMost(nums, k-1)
}

func atMost(nums []int, k int) int {
    l, ans := 0, 0
    for r := 0; r < len(nums); r++ {
        if nums[r]%2 == 1 {
            k--
        }
        for k < 0 {
            if nums[l]%2 == 1 {
                k++
            }
            l++
        }
        ans += r - l + 1
    }
    return ans
}
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    int atMost(vector<int>& nums, int k) {
        int l = 0, ans = 0;
        for (int r = 0; r < (int)nums.size(); r++) {
            if (nums[r] % 2 == 1) k--;
            while (k < 0) {
                if (nums[l] % 2 == 1) k++;
                l++;
            }
            ans += r - l + 1;
        }
        return ans;
    }
};
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def at_most(k: int) -> int:
            l = 0
            ans = 0
            for r, v in enumerate(nums):
                if v % 2 == 1:
                    k -= 1
                while k < 0:
                    if nums[l] % 2 == 1:
                        k += 1
                    l += 1
                ans += r - l + 1
            return ans

        return at_most(k) - at_most(k - 1)
var numberOfSubarrays = function(nums, k) {
  const atMost = (k) => {
    let l = 0, ans = 0;
    for (let r = 0; r < nums.length; r++) {
      if (nums[r] % 2 === 1) k--;
      while (k < 0) {
        if (nums[l] % 2 === 1) k++;
        l++;
      }
      ans += r - l + 1;
    }
    return ans;
  };
  return atMost(k) - atMost(k - 1);
};

Comments