24 de Março
Três somas
Como reduzir um problema de três variáveis para dois ponteiros depois de ordenar e controlar duplicatas.
Arrays e Dois Ponteiros Intermediario 25 min TypeScript
Dado um array de inteiros nums, retorne todas as tripletas [nums[i], nums[j], nums[k]] tais que:
i != ji != kj != knums[i] + nums[j] + nums[k] === 0
A resposta não pode conter tripletas duplicadas.
Exemplo:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
O que perceber antes de codar
- A resposta pede tripletas unicas, entao duplicatas importam.
- Depois de fixar um elemento, sobra um problema parecido com duas somas.
- Ordenar muda o jogo porque permite usar dois ponteiros e pular repetições.
Erros comuns
- esquecer de ordenar antes de aplicar dois ponteiros
- encontrar tripla valida e não pular valores duplicados depois
Passo 1 — Escrever a versão inicial mental sem fugir dela
A primeira leitura natural e:
- escolher um primeiro número
- escolher um segundo
- escolher um terceiro
- testar se soma zero
Isso vira tres loops.
Correto. Mas caro demais.
Passo 2 — Procurar uma redução do problema
Se você fixa nums[i], deixa de procurar tres numeros.
Agora procura só dois numeros no restante que completem:
nums[left] + nums[right] = -nums[i]
Isso já parece duas somas.
Passo 3 — Entender por que ordenar ajuda
Depois de ordenar:
- se a soma estiver pequena demais, você precisa aumentar
- se estiver grande demais, você precisa diminuir
Isso permite usar left e right.
Passo 4 — Lembrar que a resposta não aceita duplicata
Resolver a soma não basta.
Depois de achar uma tripla valida, você precisa pular valores repetidos para não gerar a mesma resposta de novo.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function threeSum(nums: number[]): number[][] {
// sua solução aqui
return []
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n²)
Espaço: O(1)
Solução 1 — Tres loops O(n³)
Boa versão inicial para mostrar o problema bruto.
export function threeSum(nums: number[]): number[][] {
const result: number[][] = []
const seen = new Set<string>()
for (let i = 0; i < nums.length; i += 1) {
for (let j = i + 1; j < nums.length; j += 1) {
for (let k = j + 1; k < nums.length; k += 1) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b)
const key = triplet.join(',')
if (!seen.has(key)) {
seen.add(key)
result.push(triplet)
}
}
}
}
}
return result
}Funciona, mas e pesado demais.
Solução 2 — Ordenação + dois ponteiros O(n²)
Agora o problema de tres numeros vira um problema de dois numeros repetido para cada indice fixo.
export function threeSum(nums: number[]): number[][] {
const sorted = [...nums].sort((a, b) => a - b)
const result: number[][] = []
for (let index = 0; index < sorted.length - 2; index += 1) {
const value = sorted[index]
if (index > 0 && value === sorted[index - 1]) {
continue
}
let left = index + 1
let right = sorted.length - 1
while (left < right) {
const sum = value + sorted[left] + sorted[right]
if (sum === 0) {
result.push([value, sorted[left], sorted[right]])
left += 1
right -= 1
while (left < right && sorted[left] === sorted[left - 1]) {
left += 1
}
while (left < right && sorted[right] === sorted[right + 1]) {
right -= 1
}
continue
}
if (sum < 0) {
left += 1
} else {
right -= 1
}
}
}
return result
}O passo importante aqui não e o sort isolado. E o que ele permite fazer depois.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial testa todas as triplas e custa
O(n³). A versão melhor ordena o array, fixa um elemento e reduz o resto para um problema de dois ponteiros. Assim eu ajusto a soma andandolefterighte ainda controlo duplicatas durante a passada.
Isso mostra que você:
- soube decompor o problema
- conectou tres somas a um padrão que já conhecia
- explicou a deduplicação como parte da regra, não como detalhe solto
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- fixar uma parte da resposta e resolver o resto
- combinar ordenação com dois ponteiros
- controlar duplicatas em problemas de combinação
- reduzir dimensao de busca com estrutura
O ponto não e decorar esse problema.
O ponto e aprender a reduzir um problema maior para um menor já conhecido.