Bem-vindo de volta à nossa série de blogs sobre solução de problemas na engenharia de software moderna!

Na Parte 1, exploramos o Padrão de contador de frequência, uma técnica poderosa para otimizar algoritmos contando eficientemente a frequência dos elementos. Se você perdeu ou deseja uma atualização rápida, sinta-se à vontade para conferir antes de continuar.

Nesta parte, mergulharemos em outro padrão essencial: o Padrão Multiponto. Esse padrão é inestimável ao lidar com cenários onde vários elementos precisam ser comparados, pesquisados ​​ou percorridos simultaneamente. Vamos explorar como funciona e onde você pode aplicá-lo para melhorar a eficiência do seu código.

02. Padrão Multiponto

O Padrão Multiponto é uma técnica usada no projeto de algoritmos onde vários ponteiros (ou iteradores) são empregados para percorrer estruturas de dados como arrays ou listas vinculadas. Em vez de depender de um único ponteiro ou loop, esse padrão usa dois ou mais ponteiros que se movem pelos dados em velocidades diferentes ou a partir de pontos de partida diferentes.

Exemplo de problema

Escreva uma função chamada sumZero que aceite um array classificado de números inteiros. A função deve encontrar o primeiro par onde a soma é zero. Se tal par existir, retorne uma matriz que inclua ambos os valores; caso contrário, retorne indefinido.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Solução Básica

function sumZero(arr){
    for (let i = 0; i 



Complexidade de tempo - O(N^2)

Solução usando padrão multiponto

etapa 1: Entenda o problema

Precisamos encontrar dois números em um array **sorted que somam zero. Como o array está classificado, podemos aproveitar essa ordem para encontrar a solução com mais eficiência.

etapa 2: inicializar dois ponteiros

Configure dois ponteiros: um (esquerda) começando no início do array e o outro (direita) começando no final.

Exemplo:


Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5




Etapa 3: Calcule a soma dos valores nos ponteiros

Adicione os valores nos ponteiros esquerdo e direito para obter a soma


Sum = -4   5 = 1




Etapa 4: compare a soma com zero

• Se a soma for maior que zero: Mova o ponteiro direito um passo para a esquerda para diminuir a soma.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• Se a soma for menor que zero: Mova o ponteiro esquerdo um passo para a direita para aumentar a soma.

New Sum = -4   2 = -2
Sum is -2 



Etapa 5: Repita o processo

Continue movendo os ponteiros e calculando a soma até que eles se encontrem ou um par seja encontrado.


New Sum = -3   2 = -1
Sum is -1 



A soma é zero, então a função retorna [-2, 2].

Se o loop for concluído sem encontrar esse par, retorne indefinido.

Código Final


function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left  0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left  ;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}




OBSERVAÇÃO:
Complexidade de tempo: O(n) – A função é eficiente e dimensiona linearmente com o tamanho da matriz.
Complexidade espacial: O(1) – A função usa uma quantidade mínima de memória adicional.

Conclusão

O Padrão Multiponto é uma técnica poderosa para resolver problemas que envolvem pesquisa, comparação ou manipulação de elementos em uma estrutura de dados classificada. Ao usar vários ponteiros que se movem uns em direção aos outros, podemos melhorar significativamente a eficiência dos algoritmos, reduzindo a complexidade do tempo de O(n²) para O(n) em muitos casos. Esse padrão é versátil e pode ser aplicado a uma ampla gama de problemas, tornando-o uma estratégia essencial para otimizar o desempenho do seu código.

Fique ligado em nosso próximo post, onde nos aprofundaremos no Sliding Window Pattern, outra ferramenta essencial para resolver problemas envolvendo segmentos de dados dinâmicos. É um padrão incrivelmente útil que pode ajudá-lo a resolver desafios ainda mais complexos com facilidade!