Solução Informática Intermediário - Semana 49

Solução de Lúcio Cardoso

Imagine que, para um índice fixo $i$ do vetor, sabemos o primeiro índice $j \geq i$ tal que o subvetor $[i..j]$ possui exatamente $K$ valores distintos. Então, por consequência, para todo índice $l \geq j$, o subvetor $[i..l]$ possuirá pelo menos $K$ valores distintos. Logo, há exatamente $N-j+1$ subvetores que satisfazem a condição do enuncidado e que começam em $i$. Assim, para resolver o problema, basta calcular tal índice $j$ para cada índice $i$ do vetor e somar $N-j+1$ na resposta a cada vez.

Para isso, vamos criar dois "ponteiros" (que na verdade apenas representam posições no vetor), $l$ e $r$. Imagine que para o $l$ atual queremos encontrar o primeiro valor de $r \geq l$ tal que $[l..r]$ possui $K$ elementos distintos. Se $[l..r]$ possuir menos que $K$ elementos distintos, aumentamos o valor de $r$ em 1; fazemos isso até que $r$ seja o índice desejado. Assim, como dito acima, haverão $N-r+1$ subvetores que começam em $l$ e que satisfaçam a condição do problema. Depois disso, repetimos o processo para os próximos valores de $l$. A observação importante é que não precisamos diminuir o índice $r$ em nenhum momento, já que para índices $l$ maiores, a posição $r$ desejada só irá aumentar.

Como os índices $l$ e $r$ só irão aumentar, $l$ percorrerá cada posição do vetor exatamente uma vez, assim como $r$. Então, a complexidade final será $O(2n)$ = $O(n)$. Para mais detalhes da implementação, confira o código abaixo: