3Sum

Najpierw posortuj listę. Wtedy dowolne trzy pozycje i < j < k dają wartości, które są już uporządkowane, nums[i] ≤ nums[j] ≤ nums[k], więc trójka jest zapisana poprawnie w chwili, gdy ją znajdziesz. Trzy zagnieżdżone pętle odwiedzają każdy wybór pozycji, więc żadna trójka nie zostanie pominięta.

Teraz powtórzenia. Pierwszy posortowany przykład to [-2, -1, 0, 1, 1, 2], a [-1, 0, 1] może pobrać swoją jedynkę z indeksu 3 albo indeksu 4. Każda pętla pomija więc pozycję, której wartość jest równa wartości wypróbowanej wcześniej przez tę samą pętlę. Każda pętla wypróbowuje wtedy każdą odrębną wartość tylko raz, a każda odrębna trójka pojawia się raz, już w posortowanej kolejności. Pomijanie porównuje tylko z poprzednią pozycją wewnątrz tej samej pętli, więc [-2, 1, 1] nadal wykorzystuje obie jedynki.

Problemem jest koszt. Istnieje około n³/6 trójek: dla 3000 liczb daje to 4.5 × 10^9 sum, czyli znacznie więcej, niż pozwala jakikolwiek limit czasu.

Gdy pierwsza wartość nums[i] jest ustalona, potrzebujesz dwóch kolejnych wartości, których suma wynosi -nums[i]. To problem Two Sum. Przesuwaj j w prawo od i i przechowuj w zbiorze wartości, które minąłeś. Dla każdego j brakująca wartość to need = -nums[i] - nums[j]. Jeśli need znajduje się w zbiorze, [nums[i], need, nums[j]] daje w sumie 0. Wyszukiwanie w zbiorze ma średni koszt O(1), więc dla jednego i koszt wynosi O(n), a dla całego wyszukiwania O(n²).

Sortowanie nadal pomaga zarządzać przetwarzaniem. Pomiń i, jeśli jego wartość jest taka sama jak poprzedniej. Po znalezieniu dopasowania przesuń j za wszystkie wystąpienia nums[j]: gdy pierwsza i trzecia wartość są ustalone, środkowa również jest ustalona, więc kolejna taka sama wartość mogłaby jedynie powtórzyć tę samą trójkę. Ponieważ need pochodzi z wcześniejszej pozycji na posortowanej liście, need ≤ nums[j], a wartości w trójce są uporządkowane. Możesz też przerwać, gdy tylko nums[i] > 0: dwie kolejne wartości są co najmniej tak duże, więc suma nie może wynieść 0.

Jeden szczegół: gdy j przesuwa się w prawo, nums[j] rośnie, a need maleje, więc dla jednego i trójki pojawiają się w kolejności malejących wartości środkowych. Dla [-2, -1, 0, 1, 1, 2] przy i = 0 znajdujesz [-2, 1, 1] przy drugim 1, a następnie [-2, 0, 2] przy 2. Odwróć każdą grupę, zanim dodasz ją do odpowiedzi. Wersje C i R oznaczają widziane wartości w tablicy indeksowanej wartością zamiast w zbiorze haszującym, co działa, ponieważ każda wartość mieści się w zakresie ±10^5.

Posortowana kolejność może zastąpić zbiór. Ustal nums[i], ustaw lo na i+1, a hi na ostatnim indeksie, i sprawdź nums[i] + nums[lo] + nums[hi]. Jeśli suma jest mniejsza od 0, potrzebujesz większej wartości, więc lo przesuwa się w prawo. Jeśli jest większa od 0, potrzebujesz mniejszej wartości, więc hi przesuwa się w lewo. Gdy suma wynosi dokładnie 0, zapisz trójkę i przesuń oba wskaźniki.

Żadna trójka nie zostanie pominięta. Gdy suma jest mniejsza od 0, nums[lo] jest za małe nawet w połączeniu z największą pozostałą wartością, nums[hi], więc nie może utworzyć pary z żadną wartością, która nadal mieści się w zakresie, a pominięcie go niczego nie tracisz. Suma większa od 0 to sytuacja odwrotna: nums[hi] jest za duże nawet w połączeniu z najmniejszą pozostałą wartością. W każdym kroku jedna wartość zostaje ostatecznie pominięta, więc dla jednego i potrzeba najwyżej n kroków, a całe wyszukiwanie ma złożoność O(n²) i nie wymaga pamięci poza sortowaniem i wynikiem.

Weź posortowaną tablicę [-2, -1, 0, 1, 1, 2]. Dla i = 0 (wartość -2) lo zaczyna od -1, a hi od 2: suma wynosi -1, więc lo przesuwa się na 0. Teraz -2 + 0 + 2 = 0, więc zapisujesz [-2, 0, 2], a oba wskaźniki trafiają na dwie jedynki, które dają [-2, 1, 1]. Dla i = 1 (wartość -1) wartości 0 i 2 dają sumę 1, więc hi przesuwa się na drugą jedynkę, a -1 + 0 + 1 = 0 pozwala zapisać [-1, 0, 1]. Wartość 0 przy i = 2 nie daje żadnego wyniku, a przy i = 3 wartość jest dodatnia, więc wyszukiwanie się kończy.

Powtarzające się wartości wymagają dwóch reguł. Pomiń i, którego wartość jest równa poprzedniej. Po znalezieniu wyniku przesuń lo za kolejne wystąpienia użytej wartości. Dla hi nie jest potrzebna osobna reguła: gdy lo wskazuje większą wartość, kopia poprzedniego nums[hi] daje teraz sumę większą od 0 i sama powoduje przesunięcie wskaźnika. Ponieważ i odwiedza różne wartości w kolejności rosnącej, a lo przesuwa się tylko w prawo, trójki są zwracane w posortowanej kolejności.