Two-sum ja sen monet muunnelmat
Ratkaiskaa two-sum-, three-sum-, four-sum- ja sorted array -muunnelmat hajautustauluilla ja kahdella osoittimella sekä verratkaa aika- ja tilakustannuksia.
Two-sum ja sen monet muunnelmat on ilmainen DSA Interview Prep-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu DSA Interview Prep-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Two-Sum: klassinen haastatteluongelma
LeetCode 1 'Two Sum': annettuna lajittelematon taulukko ja tavoite, palauttakaa kahden tavoitesumman muodostavan alkion indeksit. Raakavoimamenetelmä, jonka aikavaativuus on O(n²), tarkistaa kaikki parit. Optimaalinen O(n)-ratkaisu käyttää hajautustaulua: tarkistakaa jokaiselle alkiolle x, löytyykö target - x jo taulukosta. Jos löytyy, palauttakaa indeksipari. Muussa tapauksessa tallentakaa x ja sen indeksi hajautustauluun.
Two-Sum on usein haastattelun ensimmäinen tehtävä — sen täydellinen hallinta osoittaa, että olette valmiita siirtymään vaikeampiin ongelmiin.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Miksi hajautustaulu toimii Two-Sum-ongelmassa
Hajautustauluun tallennetaan kaikki tähän mennessä nähdyt alkiot. Kun käsittelette alkiota x, nämä kaksi alkiota muodostavat kelvollisen parin, jos target - x löytyy hajautustaulusta. Tärkeää on, että komplementti tarkistetaan aina ennen x:n tallentamista. Näin estetään tilanne, jossa yksi alkio yhdistetään itseensä (esimerkiksi jos x == target/2, hajautustaulu tarkistetaan ennen x:n tallentamista, joten x ei täsmää, ellei taulukossa ole kahta kopiota).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iTwo-Sum lajitellussa taulukossa (kaksi osoitinta)
Jos taulukko on jo lajiteltu ja tarvitsette arvojen indeksit (ettekä alkuperäisiä indeksejä), käyttäkää kahden osoittimen tekniikkaa: left- ja right-osoittimet aloittavat vastakkaisista päistä. Jos summa on tavoitteen suuruinen, palauttakaa tulos. Jos summa on liian pieni, siirtäkää left-osoitinta oikealle. Jos summa on liian suuri, siirtäkää right-osoitinta vasemmalle. Aikavaativuus on O(n) ja tilavaativuus O(1) — tämä on hajautustauluratkaisua parempi, kun taulukko on lajiteltu ja muistia on rajoitetusti.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Three-Sum (LeetCode 15)
LeetCode 15 'Three Sum': etsikää kaikki yksikäsitteiset kolmikot, joiden summa on nolla. Lajitelkaa taulukko, kiinnittäkää yksi alkio kerrallaan ja käyttäkää kahta osoitinta jäljelle jäävässä lajitellussa osataulukossa. Ohittakaa toistuvat arvot, jotta ette tuota samoja kolmikoita useita kertoja. Aikavaativuus on O(n²) — tämä on ongelman kannalta optimaalinen, koska tulos voi itsessään sisältää O(n²) kolmiota.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Four-Sum (LeetCode 18)
LeetCode 18 'Four Sum': etsikää kaikki yksikäsitteiset nelikot, joiden summa on target. Laajentakaa Three-Sum-mallia: kiinnittäkää kaksi alkiota kahdella sisäkkäisellä silmukalla (ohittaen duplikaatit) ja käyttäkää sitten kahta osoitinta sisemmässä osataulukossa. Aikavaativuus on O(n³). Yleisesti k-sum-ongelmassa rekursiota käytetään k-2 kertaa ja sen jälkeen kahta osoitinta, jolloin aikavaativuus on O(n^(k-1)).
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Two-Sum lähimpänä tavoitetta
Yleinen muunnelma: etsikää pari, jonka summa on lähimpänä tavoitetta (summan ei tarvitse olla täsmälleen tavoitteen suuruinen). Lajitelkaa taulukko ja käyttäkää kahta osoitinta. Pitäkää kirjaa tähän asti lähimpänä olevasta summasta ja päivittäkää sitä aina, kun löydätte parin, jonka absoluuttinen erotus tavoitteesta on pienempi. Tämä lajittelun jälkeen suoraviivainen ratkaisu toimii ajassa O(n log n).
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!Two-Sum useilla pareilla (kaikki parit)
Kun haluatte löytää kaikki tavoitesumman muodostavat parit, lajitelkaa taulukko ja käyttäkää kahta osoitinta keräten kaikki parit. Kun olette löytäneet kelvollisen parin, ohittakaa duplikaatit molemmista päistä ennen jatkamista. Lajittelu vie aikaa O(n log n) ja läpikäynti O(n), joten kokonaisaikavaativuus on O(n log n). Myös hajautustaulua voi käyttää parien keräämiseen, mutta duplikaatit on käsiteltävä huolellisesti.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]Laske parit, joiden summa on pienempi kuin K
Toinen muunnelma: laskekaa, kuinka monen parin summa on pienempi kuin k. Lajitelkaa taulukko ja käyttäkää kahta osoitinta. Kun nums[lo] + nums[hi] < k, kaikki parit (lo, lo+1), (lo, lo+2), ..., (lo, hi) ovat kelvollisia — niitä on hi - lo kappaletta. Siirtäkää lo-osoitinta eteenpäin. Muussa tapauksessa pienentäkää hi-arvoa. Kokonaisaikavaativuus on lajittelun O(n log n) ja laskennan O(n) eli yhteensä O(n log n).
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifyTwo-Sum hajautustaululla: duplikaattien käsittely
Kun sama arvo voi esiintyä useita kertoja ja tarvitsette kelvollisten parien lukumäärän (ette vain tietoa niiden olemassaolosta), tallentakaa hajautustauluun esiintymien lukumäärät. Jos parin molemmat alkiot ovat samoja, frekvenssin f tuottamien parien määrä on f*(f-1)//2. Jos parin alkiot ovat erisuuria, kertokaa niiden frekvenssit keskenään. Näin kaikki kelvolliset parit voidaan laskea ajassa O(n).
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Two-Sum-mallin muunnelmien tunnistaminen
Two-Sum-malli esiintyy monissa muodoissa. Tunnistakaa se, kun tehtävässä pyydetään etsimään vähintään kaksi alkiota, jotka täyttävät numeerisen ehdon (summa, tulo tai erotus). Perusstrategia on aina: kiinnittäkää yksi alkio ja etsikää sen komplementti valmiiksi lasketusta rakenteesta (hajautustaulusta tai lajitellusta taulukosta osoittimen avulla). Laajentakaa malli k-summaan kiinnittämällä k-2 alkiota sisäkkäisillä silmukoilla ja soveltamalla perustapausta.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Two-Sum-ongelman ratkaisemisesta kertominen haastattelussa
Kun Two-Sum tulee vastaan haastattelussa, käykää ajattelunne ääneen läpi: 'Tarvitsen kaksi lukua, joiden summa on target. Jokaisen luvun x kohdalla minun on tarkistettava, löytyykö target-x. Voin tehdä tarkistuksen hajautustaululla ajassa O(1), jolloin kokonaisaikavaativuus on O(n) ja tilavaativuus O(n). Jos taulukko olisi lajiteltu, voisin vaihtoehtoisesti käyttää kahta osoitinta O(1) lisätilassa.' Esittäkää molemmat lähestymistavat ja kysykää tilarajoituksista ennen valintaa.
Pikatesti
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin yhteenveto
Oppitunnilla opitte: two-sum hyödyntää hajautustaulua täydentävän arvon olemassaolon tarkistamiseen ajassa O(1), joten kokonaisaika on O(n), järjestetyissä taulukoissa kaksi osoitinta saavuttaa O(1)-tilankulutuksen ja three-sum ja four-sum pelkistyvät two-sum-ongelmaksi lajittelun ja sisäkkäisten silmukoiden avulla; niiden aikavaativuudet ovat vastaavasti O(n²) ja O(n³). Seuraavaksi tutustumme esiintymien laskennan malleihin sekä ryhmittelyyn defaultdict- ja Counter-rakenteilla.
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Two-sum ja sen monet muunnelmat” ilmainen?
Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa DSA Interview Prep-oppimispolun 3 oppituntia, myös oppitunnin “Two-sum ja sen monet muunnelmat”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Two-sum ja sen monet muunnelmat”?
Ratkaiskaa two-sum-, three-sum-, four-sum- ja sorted array -muunnelmat hajautustauluilla ja kahdella osoittimella sekä verratkaa aika- ja tilakustannuksia. Harjoittelet DSA Interview Prep-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni DSA Interview Prep-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin DSA Interview Prep-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Two-sum ja sen monet muunnelmat”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä DSA Interview Prep-oppitunnilla?
Kyllä. Jokainen DSA Interview Prep-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Hajautusfunktion sisäinen toiminta ja törmäysten käsittely
- Two-sum ja sen monet muunnelmat
- Frekvenssien laskeminen ja ryhmittely
- Pisin peräkkäinen jono ja LRU-välimuisti