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: