Solução Informática - Nível Intermediário - Semana 33

Solução escrita por Caique Paiva

Conhecimento prévio necessário:

• Two Pointers

Vamos primeiro resolver o seguinte problema primeiro:

Dado um vetor $A_1, A_2, ..., A_N$, encontre uma dupla $(i,j)$ tal que $A_i+A_j = X$ e $i \ne j$ ou diga que não existe nenhuma.

Para resolver, primeiro ordene o vetor em ordem crescente. Então, coloque um ponteiro no final da lista (Chamado de $r$) e outro no começo (Chamado de $l$), e faça o seguinte algoritmo:

• Se $A_l + A_r = X$, então conseguimos o que queríamos.
• Se $A_l + A_r > X$, então, faça $r--$, e dai a soma atual de $A_l + A_r$ vai diminuir, pois $A_r < A_{r+1}$.
• Se $A_l + A_r < X$, então, faça $l++$, e dai a soma atual de $A_l + A_r$ vai aumentar, pois $A_l < A_{l+1}$.

Se $l >= r$ em algum momento, então paramos o algoritmo. Esse algoritmo funciona pois, se existe uma dupla $(i, j)$, então, primeiro que o algoritmo passa por todos os índices do vetor, logo, alguma das duas coisas vai acontecer primeiro, ou $l = i$, ou $r = j$, então, suponha sem perda de generalidade que o que acontece primeiro é que $l = i$, e logo $r > j$, pois $l = i$ aconteceu primeiro. Portanto, como $l = i$, temos que a soma atual é $A_i + A_r > X$, então, vamos sempre diminuir o $r$ até ele chegar no $j$, logo, nós sempre chegamos na dupla desejada, se ela existir.

Esse algoritmo roda em $O(N)$.

Vamos resolver o problema original agora.

Primeiro, vamos ordenar o vetor por ordem crescente. Agora, veja que queremos achar uma tripla tal que $A_i + A_j = X - A_k$, portanto, vamos variar $k$ começando por $1$ e indo até $N$, e para cada $k$, vamos procurar uma dupla $(i, j)$ tal que $A_i + A_j = X - A_k$, com $i \neq j, j \neq k, k \neq i$. Sabemos como fazer isso em $O(N)$, então, como fazemos isso para cada $k$ entre $1$ a $N$, conseguimos fazer isso em $O(N^2)$.

Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.