Solução Informática - Nivel Avançado - Semana 22

Escrito por Lúcio Figueiredo

Conhecimento prévio necessário:

• Map

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: