Escrito por Lúcio Figueiredo
Conhecimento prévio necessário:
Imagine que existem quatro índices do vetor $$i, j, k, l$$ de modo que $$v[i] + v[j] + v[k] + v[l] = x$$. Assuma que $$i > j > k > l$$. Vamos fixar os índices $$i$$ e $$j$$, ou seja, em $$O(n^2)$$, vamos iterar por cada par de índices do vetor e fixá-los como $$i$$ e $$j$$. Agora, queremos descobrir se existe um par $$k, l$$ de modo que $$k$$ e $$l$$ sejam menores que $$i$$ e $$j$$ e de modo que a soma dos 4 índices seja $$x$$, ou seja, $$v[k] + v[l] + v[i] + v[j] = x \implies v[k] + v[l] = x – v[i] – v[j]$$.
Para encontrar os índices $$(k, l)$$ (se existirem), podemos utilizar um map de inteiros para pares que guarda, para cada soma $$S$$, um par de índices com tal soma (ou seja, $$map[S] = (k, l)$$ tal que $$v[k] + v[l] = S$$). Para garantir que os índices $$i, j, k, l$$ serão distintos, é necessário cuidado ao armanezar os valores no map. Iremos iterar por cada indíce $$i$$ de $$1$$ a $$N$$ mantendo a propriedade de que armazenamos no map todas as somas utilizando apenas índices menores que $$i$$. Assim, dentro do loop que itera pelo índice $$i$$, podemos fixar o índice $$j > i$$ e tentar encontrar, usando o map, um par de inteiros com soma igual a $$x – v[i] – v[j]$$. Caso seja possível encontrar tal soma no map, conseguimos encontrar 4 índices com soma igual a $$x$$: $$i, j$$ e o par contido em $$map[x – v[i] – v[j]]$$.
Caso não encontremos os 4 índices utilizando o indíce $$i$$, temos que incluir no map as somas com $$v[i]$$ e $$v[j]$$ para $$j < i$$. Para isso, basta iterar por todo $$j < i$$ e indicar que $$map[v[i] + v[j]] = (i, j)$$. Agora que o map foi atualizado, podemos tentar encontrar uma soma igual a $$x$$ que utiliza índices maiores que $$i$$. A complexidade final da solução é $$O(n^2 \log_{} n)$$, já que utilizamos um map dentro de loops em $$O(n^2)$$. Confira o código abaixo para melhor entendimento: