Untitled

 avatar
unknown
plain_text
a month ago
1.2 kB
0
Indexable
import java.util.HashMap;

public class GoodSubarrays {
    public static int countGood(int[] nums, int k) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        int i = 0, j = 0, pairs = 0, result = 0;

        while (j < nums.length) {
            // Expand the window by including nums[j]
            freq.put(nums[j], freq.getOrDefault(nums[j], 0) + 1);
            pairs += freq.get(nums[j]) - 1; // Increment pairs contributed by nums[j]

            // Shrink the window until pairs < k
            while (pairs >= k) {
                result += nums.length - j; // Count all subarrays ending at j
                freq.put(nums[i], freq.get(nums[i]) - 1); // Remove nums[i] from the window
                pairs -= freq.get(nums[i]); // Decrease pairs contributed by nums[i]
                i++; // Shrink the window
            }

            j++; // Expand the window
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(countGood(new int[]{1, 1, 1, 1, 1}, 10)); // Output: 1
        System.out.println(countGood(new int[]{3, 1, 4, 3, 2, 2, 4}, 2)); // Output: 4
    }
}
Leave a Comment