Dois ponteiros e janela deslizante

Dois ponteiros

Com o array ordenado, um ponteiro no início e outro no fim: se a soma passou do alvo, só diminuir ajuda (R anda para trás); se faltou, só aumentar ajuda (L anda para frente). Cada passo descarta uma posição, então são no máximo n passos — O(n) em vez de testar todos os pares, O(n²). A mesma ideia remove duplicados em uma lista ordenada e inverte arrays no lugar.

Janela deslizante

Para perguntas sobre trechos seguidos (subarray, substring), mantenha uma janela [L, R]. Ao avançar R, some o que entrou; ao avançar L, subtraia o que saiu. Janela fixa: maior soma de k dias seguidos. Janela variável: maior substring sem letra repetida, menor trecho que soma pelo menos X. Cada elemento entra e sai uma vez: O(n).

Quando pensar nisso

Sinais: "array ordenado", "par/trio que soma", "subarray contínuo", "substring", "k elementos seguidos". Se a pergunta é sobre qualquer subconjunto (não contínuo), a janela não serve — aí costuma ser hash ou programação dinâmica.

// O(n · k): soma k itens de novo para cada posição
function maiorSoma(v: number[], k: number): number {
  let melhor = -Infinity;
  for (let i = 0; i + k <= v.length; i++) {
    let s = 0;
    for (let j = i; j < i + k; j++) s += v[j];
    melhor = Math.max(melhor, s);
  }
  return melhor;
}

// O(n): a janela anda uma casa — entra v[r], sai v[r - k]
function maiorSoma(v: number[], k: number): number {
  let s = 0;
  for (let r = 0; r < k; r++) s += v[r];
  let melhor = s;
  for (let r = k; r < v.length; r++) {
    s += v[r] - v[r - k];
    melhor = Math.max(melhor, s);
  }
  return melhor;
}