LeetCode 2537: Count the Number of Good Subarrays

Explanation:

To solve this problem, we can use a sliding window approach along with prefix sums to efficiently count the number of good subarrays. We iterate through the array while maintaining a window of elements such that the number of matching pairs within the window is at least k. By keeping track of the frequency of each element in the window using a HashMap, we can determine the number of pairs within the window.

Algorithmic Idea:

1. Initialize variables: count (to store the number of good subarrays), prefixSum (to store the prefix sum of the array elements), windowStart (start of the window), and a HashMap to keep track of the frequencies of elements in the window.
2. Iterate through the array:
   • Update the prefix sum at the current index.
   • Calculate the number of pairs within the window by subtracting the prefix sum at the current index by k and check if the count of this value exists in the HashMap. If it does, increment count by the count of that value in the HashMap.
   • Increment the count of the current prefix sum in the HashMap.
3. Return the final count.

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input array nums.

Space Complexity:

The space complexity of this solution is O(n) to store the prefix sum and the HashMap.

:

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int count = 0;
        int prefixSum = 0;
        int windowStart = 0;
        Map<Integer, Integer> freqMap = new HashMap<>();
        freqMap.put(0, 1);

        for (int num : nums) {
            prefixSum += num;
            if (freqMap.containsKey(prefixSum - k)) {
                count += freqMap.get(prefixSum - k);
            }
            freqMap.put(prefixSum, freqMap.getOrDefault(prefixSum, 0) + 1);
        }

        return count;
    }
}