K-komplementarne pary z JavaScript

ostatnio miałem okazję podjąć wyzwanie kodowe dla firmy, którą naprawdę podziwiam i z którą chciałbym kiedyś pracować. Byłem wdzięczny, podekscytowany, a tym bardziej niespokojny, ponieważ było wiele niewiadomych, które brały udział w Wyzwaniu dotyczącym kodu. Rzeczywistość jest taka, że tylko tyle można zrobić, aby przygotować:

• buduj projekty
• Badaj algorytmy
• szlifuj problemy: LeetCode, HackerRank, CodeSignal

jednak jedynym sposobem, aby dowiedzieć się, czy jesteś gotowy, czy nie, jest skok na głęboką wodę, aby zobaczyć, czy możesz się unosić. Tak zrobiłem i nauczyłem się o wiele więcej, niż kiedykolwiek wcześniej, i dlatego chciałem się tym podzielić.

na początku zadania miałem do wykonania trzy zadania. Skupię się tylko na 1 z nich w tym blogu — K-komplementarne pary.

cel

• otrzymujesz docelową liczbę całkowitą i tablicę pełną dodatnich liczb całkowitych
• musisz znaleźć i zlokalizować dopełnienie docelowej liczby całkowitej-co oznacza, że wartość jednego indeksu i drugiego indeksu musi być równa celowi
• zwróć liczbę par na końcu

numberArray + numberArray = 7

powyższe byłoby poprawną parą, ponieważ te dwie wartości są równe celowi.

pierwsze podejście

kiedy po raz pierwszy podszedłem do tego problemu, poszedłem za nim w brutalny sposób. Pomyślałem, że mogę użyć zagnieżdżonych pętli, aby sprawdzić pary uzupełniające, i hej, miałem rację! Faktycznie zadziałało:

Jak to działa?

• zapętlasz elementy początkowej tablicy.
• następnie zapętlasz go, aby sprawdzić, czy jest równy celowi w każdym przejściu.
• jeśli cel jest zgodny, liczba jest zwiększana.

chociaż działa, a ja otrzymałem dokładną liczbę komplementarnych par, biorąc pod uwagę cel, nie był idealny. W rzeczywistości zagnieżdżone pętle są powolne i mogą rosnąć wykładniczo przy większych tablicach elementów. Złożoność czasowa dla niego to O (N2).

drugie podejście-Optymalizacja

więc wróciłem do deski kreślarskiej. Po pewnych badaniach i rozważaniach odkryłem, że mogę przechowywać wartości w obiekcie – {key: value}.

teraz, to było nadal bardzo trudne, zwłaszcza, że nigdy wcześniej nie napisałem czegoś tak złożonego. Stąpałem po nowym terytorium, ale byłem podekscytowany, ponieważ byłem w stanie zoptymalizować mój poprzedni algorytm do O (N):

więc jak to działa?

• sprawdź, czy istnieje liczba lub długość.
• najpierw uruchamiamy numberArray, aby utworzyć pary klucz / wartość w obiekcie located_pairs. W trakcie tego procesu będzie sprawdzać unikalność i duplikaty.
• następnie przejeżdżamy po kluczach zlokalizowanego obiektu i sprawdzamy, czy robi to z celem. Jeśli tak, liczba par jest zwiększana.