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

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: