K-Pares Complementares com JavaScript

recentemente, tive a oportunidade de fazer um código desafio para uma empresa que eu realmente admiro, e gostaria de trabalhar para um dia. Eu estava grato, animado, e ainda mais ansioso porque havia muitas incógnitas indo para o desafio do Código. A realidade é que não há muito que possas fazer para te preparares.:

• projectos Build
• algoritmos de estudo
• problemas de moagem: LeetCode, HackerRank, CodeSignal

no Entanto, a única maneira de descobrir se você está ou não pronto para saltar para o fundo para ver se você pudesse flutuar. Então eu fiz, e eu aprendi muito mais do que eu já tive antes, e por causa disso eu queria compartilhá-lo.

no início da missão eu estava diante de três tarefas para completar. Vou concentrar – me em apenas um destes neste blog — K-pares complementares.

Objetivo

• Você for dado Destino Inteiro e uma Matriz completa de números Inteiros positivos
• Você precisa encontrar e localizar o complemento para o Destino Inteiro — o que significa que o valor de um índice e outro índice DEVE ser igual a de Destino
• Retornar a contagem dos pares no final

numberArray + numberArray = 7

acima seria válido par uma vez que estes dois valores iguais a de destino.

First Approach

When I first approached this issue, I went after it in a brute force manner. Pensei que podia usar aninhados para verificar os pares complementares, e eu tinha razão! Ele realmente trabalhou:

Como funciona?

• loop sobre os elementos da matriz inicial.
• depois passa por cima dela em uníssono para verificar se é ou não igual ao alvo através de cada passagem.
• se o alvo for um fósforo, a contagem é incrementada.

While it works, and I did receive an accurate count of the complementary pairs given a target, it was not ideal. A realidade é que os laços aninhados são lentos, e podem crescer exponencialmente dado conjuntos maiores de elementos. A complexidade de tempo para ele é O (N2).

segunda abordagem — optimização

por isso voltei ao desenho. Depois de alguma pesquisa e consideração, eu descobri que eu poderia armazenar os valores em um objeto — {chave: valor}.Agora, isto ainda era muito complicado, especialmente porque nunca escrevi algo tão complexo antes. Eu estava pisando em um território novo, mas eu estava animado porque eu era realmente capaz de otimizar o meu ex-algoritmo de tempo O(N):

Então como é que funciona?

• Vet que quantidade ou o comprimento é existente.
• nós corremos através do Number array primeiro para criar pares chave / valor no objeto located_pairs. Ao longo deste processo, verificará a singularidade e as duplicações.
• então passamos sobre as chaves do objeto localizado e vet para saber se ele faz ou não com o alvo. Se o fizer, a contagem de pares é incrementada.