Untitled
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