Competitive Programming Academy · Lekcja

Znajdowanie pary o zadanej sumie

Pokonanie brutalnego O(n^2)

Znajdowanie pary o zadanej sumie to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Problem sumy pary

Mając tablicę i wartość docelową, należy znaleźć dwie wartości, które dają w sumie tę wartość. To jedno z najczęstszych zadań rozgrzewkowych w konkursach programistycznych. 🔍

Podejście siłowe

Najbardziej oczywiste rozwiązanie sprawdza każdą parę za pomocą dwóch zagnieżdżonych pętli. Działa, ale sprawdzenie wszystkich par kosztuje O(n^2) i może być zdecydowanie zbyt wolne.

for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == target:
            return (i, j)

Gdzie zawodzi brute force

Dla n bliskiego 100000 algorytm O(n^2) wykonuje dziesięć miliardów sprawdzeń, co skończy się błędem TLE. Ograniczenia wyraźnie wskazują, że należy znaleźć coś szybszego.

Sortowanie, a potem przejście

Jeśli najpierw posortują Państwo tablicę, dwa wskaźniki ustawione na obu końcach rozwiążą problem w jednym przejściu. Sortowanie kosztuje O(n log n), a następne przejście O(n).

a.sort()
left, right = 0, len(a) - 1

Porównanie z wartością docelową

W każdym kroku należy odczytać a[left] + a[right]. Ta jedna liczba bez zgadywania decyduje o następnym ruchu.

total = a[left] + a[right]

Dokładne dopasowanie: gotowe

Jeśli suma jest równa wartości docelowej, para została znaleziona. Należy od razu ją zwrócić, ponieważ potrzebna jest tylko jedna poprawna odpowiedź.

if total == target:
    return (left, right)

W przeciwnym razie należy skorygować wskaźniki

Jeśli suma jest zbyt mała, należy przesunąć left w prawo; jeśli jest zbyt duża, należy przesunąć right w lewo. Posortowana kolejność gwarantuje, że każdy ruch przybliża do celu.

elif total < target:
    left += 1
else:
    right -= 1

Para może nie istnieć

Jeśli wskaźniki się przetną, a dopasowanie nie zostanie znalezione, żadna poprawna para nie istnieje. Zakończenie pętli jest samo w sobie kompletną odpowiedzią.

Alternatywa z użyciem zbioru haszującego

Jeśli trzeba zachować oryginalne indeksy, prostszym rozwiązaniem jest zbiór haszujący: dla każdej wartości należy sprawdzić, czy target pomniejszony o tę wartość pojawił się już wcześniej.

seen = set()
for x in a:
    if target - x in seen:
        # found
        pass
    seen.add(x)

Wybór metody

Dwa wskaźniki należy stosować, gdy tablica jest posortowana lub można ją posortować; zbiór haszujący sprawdzi się, gdy potrzebne jest rzeczywiste O(n) bez sortowania albo trzeba zachować indeksy.

Należy uważać na duplikaty

Jeśli wartość może utworzyć parę z samą sobą, należy upewnić się, że oba indeksy są różne. Szybkie sprawdzenie left != right lub i != j pozwala uniknąć tego problemu.

Szybkie sprawdzenie

Chcą Państwo uzyskać rozwiązanie szybsze niż siłowe O(n^2) do znajdowania pary o sumie równej wartości docelowej.

Podsumowanie

Należy posortować tablicę, a następnie przejść ją za pomocą dwóch wskaźników, aby znaleźć parę o określonej sumie w O(n log n), lub użyć zbioru haszującego w O(n), gdy istotne są indeksy. Wybór zależy od ograniczeń. ✅

Często zadawane pytania

Czy lekcja „Znajdowanie pary o zadanej sumie” jest bezpłatna?

Tak — pełny tekst „Znajdowanie pary o zadanej sumie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Znajdowanie pary o zadanej sumie”?

Pokonanie brutalnego O(n^2) Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?

Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Znajdowanie pary o zadanej sumie”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?

Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do Competitive Programming Academy