fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scanner = new Scanner(System.in);
  6.         int n = scanner.nextInt();
  7.         int k = scanner.nextInt();
  8.         int[] arr = new int[n];
  9.  
  10.         for (int i = 0; i < n; i++) {
  11.             arr[i] = scanner.nextInt();
  12.         }
  13.  
  14.         System.out.println(countSubarrays(arr, k));
  15.     }
  16.  
  17.     public static int countSubarrays(int[] arr, int k) {
  18.         int count = 0, left = 0;
  19.         Map<Integer, Integer> freq = new HashMap<>();
  20.  
  21.         for (int right = 0; right < arr.length; right++) {
  22.             freq.put(arr[right], freq.getOrDefault(arr[right], 0) + 1);
  23.  
  24.             while (freq.size() > k) {
  25.                 freq.put(arr[left], freq.get(arr[left]) - 1);
  26.                 if (freq.get(arr[left]) == 0) {
  27.                     freq.remove(arr[left]);
  28.                 }
  29.                 left++;
  30.             }
  31.  
  32.             count += (right - left + 1);
  33.         }
  34.  
  35.         return count;
  36.     }
  37. }
  38.  
Success #stdin #stdout 0.15s 56520KB
comments (?)
stdin
copy 
3 3 
1 2 3
stdout
copy 
6
https://ideone.com/jZhvul
language:
Java (HotSpot 12)
created:
282 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!