Leetcode 2444. Count Subarrays With Fixed Bounds

[Woodyiiiiiii]

同一类型题目：

• 2444. Count Subarrays With Fixed Bounds
• 1248. Count Number of Nice Subarrays
• 2348. Number of Zero-Filled Subarrays

这一类型的题有点像滑动窗口，但不同的是窗口里可以呈辐射状，包括一些不满足条件的元素，题目最终要求满足条件的子数组数目。(Array/Sliding Window/Queue)

重点在于如何计算：三个点，起点、左端点和右端点。以最左端点为基准，右边端点每次延伸都加上左端点到起点的距离。如何计算。

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        int lb = -1, lmin = -1, lmax = -1;
        int n = nums.length;
        long count=0;

        for (int i=0; i<n; i++) {
            if (nums[i] >= minK && nums[i] <= maxK) {
                lmin = (nums[i] == minK) ? i:lmin;
                lmax = (nums[i] == maxK) ? i:lmax;
                count+= Math.max(0, Math.min(lmin, lmax) - lb);
            } else {
                lb = i;
                lmin = -1;
                lmax = -1;
            }
        }

        return count;
    }
}

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int cnt = 0, ans = 0;
        int l = -1;
        int ll = -1;
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] % 2 != 0) {
                queue.add(i);
                if (l == -1) {
                    l = i;
                }
                ++cnt;
                if (cnt > k) {
                    ll = l;
                    cnt--;
                    queue.poll();
                    l = queue.isEmpty() ? -1 : queue.peek();
                    if (cnt == k) {
                        ans += Math.max(0, l - ll);
                    }
                } else if (cnt == k) {
                    ans += Math.max(0, l - ll);
                }
            } else {
                if (cnt == k) {
                    ans += l - ll;
                }
            }
        }
        return ans;
    }
}

---

• https://leetcode.com/problems/count-subarrays-with-fixed-bounds/solutions/3254408/fast-java-solution/
• https://leetcode.cn/problems/count-number-of-nice-subarrays/solutions/211268/tong-ji-you-mei-zi-shu-zu-by-leetcode-solution/