Subarray Distinct Values

Explicación

Usamos una ventana deslizante y mantenemos un multiconjunto para registrar la frecuencia de cada elemento del arreglo. Expandimos la ventana hacia la derecha si la cantidad de elementos distintos después de expandir la ventana es menor o igual a $K$ ; si no, quitamos el elemento más a la izquierda. Cuando se agrega un elemento nuevo en el índice $i$ a una ventana cuyo elemento más a la izquierda está en el índice $j$ , crea ( $i - j$ ) subarreglos nuevos, es decir ( $j$ a $i$ ), ( $j + 1$ a $i$ ), etc., que podemos usar para calcular la cantidad de subarreglos válidos.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
	int n;
	int k;
	cin >> n >> k;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) { cin >> arr[i]; }
 
	int left = 0;
	int right = 0;
	ll ans = 0;
	int distinct = 0;
	map<int, int> freq;
	while (left < n) {
		while (right < n) {
			if (freq.count(arr[right]) == 0 && distinct == k) { break; }
 
			// Poner el nuevo elemento del arreglo en el mapa.
			if (freq.count(arr[right]) == 0) {
				freq[arr[right]] = 1;
				distinct++;
			} else {
				freq[arr[right]]++;
			}
			right++;
		}
 
		// Agregar los subarreglos nuevos.
		ans += (right - left);
 
		// Deslizar la ventana hacia la derecha.
		if (freq[arr[left]] == 1) {
			distinct--;
			freq.erase(arr[left]);
		} else {
			freq[arr[left]] -= 1;
		}
		left++;
	}
 
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class cses2428 {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int K = io.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) { arr[i] = io.nextInt(); }
 
		int left = 0, right = 0;
		long ans = 0;
		int distinct = 0;
 
		Map<Integer, Integer> freq = new HashMap<>();
		while (left < N) {
			while (right < N &&
			       (distinct + (freq.containsKey(arr[right]) ? 0 : 1) <= K)) {
				// Poner el nuevo elemento del arreglo en el mapa.
				if (!freq.containsKey(arr[right])) {
					freq.put(arr[right], 1);
					distinct++;
				} else {
					freq.put(arr[right], freq.get(arr[right]) + 1);
				}
				right++;
			}
			// Agregar los subarreglos nuevos.
			ans += (right - left);
 
			// Deslizar la ventana hacia la derecha.
			if (freq.get(arr[left]) == 1) {
				distinct--;
				freq.remove(arr[left]);
			} else {
				freq.put(arr[left], freq.get(arr[left]) - 1);
			}
			left++;
		}
 
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


n, k = map(int, input().split())
arr = list(map(int, input().split()))
left = 0
right = 0
ans = 0
distinct = 0
freq = {}
while left < n:
	while right < n:
		if arr[right] not in freq and distinct == k:
			break
 
		# Poner el nuevo elemento del arreglo en el mapa.
		if arr[right] in freq:
			freq[arr[right]] += 1
		else:
			freq[arr[right]] = 1
			distinct += 1
		right += 1
 
	# Agregar los subarreglos nuevos.
	ans += right - left
 
	# Deslizar la ventana hacia la derecha.
	freq[arr[left]] -= 1
	if freq[arr[left]] == 0:
		freq.pop(arr[left])
		distinct -= 1
	left += 1
print(ans)