1248. Count Number of Nice Subarrays.md

1248. Count Number of Nice Subarrays

Difficulty : Medium

Related Topic : Two Pointers

---

Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2:

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.

Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

Constraints:

• 1 <= nums.length <= 50000
• 1 <= nums[i] <= 10^5
• 1 <= k <= nums.length

---

Solution

• mine
  • Java
    • Two Pointers Runtime: 10 ms, faster than 71.95%, Memory Usage: 47.5 MB, less than 93.24% of Java online submissions

      // O(N)time
      // O(1)space
      public int numberOfSubarrays(int[] nums, int k) {
          int[] r  = new int[2];
          int res = 0;
          int pre = 0, cur = 0;
          for(int i = 0; i < nums.length; i++){
              r[nums[i] & 1]++;
              if(r[1] == k){
                  pre = cur;
              }
              while(r[1] == k){
                  r[nums[cur] & 1]--;
                  cur++;
              }    
              res += cur - pre;
          }
          return res;
      }
      

---

• the most votes

  • Sliding Window Runtime: 22 ms, faster than 23.47%, Memory Usage: 91.6 MB, less than 14.91% of Java online submissions

    // O(N)time
    // O(1)space
    public int numberOfSubarrays(int[] A, int k) {
        return atMost(A, k) - atMost(A, k - 1);
    }
    
    public int atMost(int[] A, int k) {
        int res = 0, i = 0, n = A.length;
        for (int j = 0; j < n; j++) {
            k -= A[j] % 2;
            while (k < 0)
                k += A[i++] % 2;
            res += j - i + 1;
        }
        return res;
    }
    

  • Runtime: 9 ms, faster than 85.69%, Memory Usage: 48.5 MB, less than 23.46% of Java online submissions

    // O(N)time
    // O(1)space
    public int numberOfSubarrays(int[] A, int k) {
        int res = 0, i = 0, count = 0, n = A.length;
        for (int j = 0; j < n; j++) {
            if (A[j] % 2 == 1) {
                --k;
                count = 0;
            }
            while (k == 0) {
                k += A[i++] & 1;
                ++count;
            }
            res += count;
        }
        return res;
    }
    

---