To pointers: modsatte ender
Brug venstre og højre pointere, der bevæger sig mod hinanden, til at løse sum af par i sorterede arrays, gyldigt palindrom og trapping rain water.
To pointers: modsatte ender er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Idéen med to pointere
To-pointer-teknikken bruger to indeksvariabler, der bevæger sig mod hinanden (eller i samme retning), for at mindske behovet for indlejrede løkker. I stedet for at kontrollere hvert par på O(n²) tid gør du fremskridt ved hver sammenligning og bliver færdig på O(n) tid. Det kræver næsten altid, at arrayet først er sorteret, fordi sorteringen gør det muligt at ræsonnere om, hvilken retning hver pointer skal flyttes i, ud fra om den aktuelle parsumm er for stor eller for lille.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []To-sum i et sorteret array
Med et sorteret array placerer du én pointer i venstre ende (den mindste værdi) og én i højre ende (den største værdi). Hvis summen er for lille, flytter du venstre pointer mod højre for at øge den. Hvis summen er for stor, flytter du højre pointer mod venstre for at mindske den. Ved hver iteration flyttes mindst én pointer, så løkken kører højst n gange: O(n) tid i alt efter sorteringen. Det er vigtigt, at hver flytning er beviseligt korrekt på grund af den sorterede rækkefølge.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Kontrol af gyldigt palindrom
En streng er et palindrom, hvis den læses ens forfra og bagfra. Brug to pointere, der begynder i hver sin ende og bevæger sig ind mod midten: sammenlign tegnene, spring ikke-alfanumeriske tegn over, og stop, når pointerne krydser hinanden. Det kører på O(n) tid med O(1) ekstra plads — langt renere end at vende strengen og sammenligne den, hvilket allokerer O(n) ekstra hukommelse.
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseTre-sum: sortér + to pointere
Tre-sum går ud på at finde alle unikke tripler, der giver summen nul. Sortér arrayet, fastlås derefter hvert element nums[i], og kør en to-pointer-søgning i det resterende delarray efter et par, der giver summen -nums[i]. Spring dubletter af både det fastlåste element og det fundne par over for at undgå gentagne tripler. Samlet tid: O(n²) efter en sortering på O(n log n).
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Beholderen med mest vand
Givet højderne af lodrette linjer skal du finde to linjer, der danner en beholder med mest muligt vand. Areal = min(height[left], height[right]) × (right - left). Flyt grådigt pointeren ved den lavere linje ind mod midten: Hvis du flytter den højere linje, kan bredden kun blive mindre, uden at højden, der begrænser arealet, øges. Dette grådige valg er beviseligt optimalt og giver O(n) tid.
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Kvadrering af et sorteret array
Kvadrér hvert element i et sorteret array, som kan indeholde negative værdier, og returnér resultatet i sorteret rækkefølge. Kvadrater af negative tal er store; kvadrater af positive tal er små nær midten. Placér to pointere i hver sin ende, og udfyld resultatarrayet fra højre mod venstre (fra størst til mindst). Det giver O(n) tid og O(n) plads til resultatet — langt bedre end først at kvadrere og derefter sortere på O(n log n) tid.
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Opsamling af regnvand
Vandet, der er fanget ved indeks i, er lig med min(max_left, max_right) - height[i]. To-pointer-tilgang: vedligehold de løbende værdier max_left og max_right. Når max_left < max_right, er venstre side flaskehalsen — behandl den venstre pointer. Ellers behandler du den højre. Det fjerner behovet for separate arrays med maksimumværdier fra venstre og højre og opnår O(1) ekstra plads.
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Hvorfor det grådige pointerskift virker
Et almindeligt opfølgende spørgsmål ved jobsamtaler er: Hvorfor er det sikkert at kassere den mindre pointer? Et bevisudkast for beholderen med mest vand: Antag, at height[left] < height[right]. Ethvert par (left, j) for j < right giver et areal ≤ height[left] × (j-left) < height[left] × (right-left) ≤ det aktuelle areal. Intet par, der begynder ved 'left' med et højreindeks under 'right', kan derfor slå det aktuelle areal. Vi kan trygt springe dem over ved at flytte left fremad.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Par med minimal forskel i sorteret array
Find det talpar i et sorteret array, der har den mindste absolutte forskel. Brug to tilstødende pointere (ikke modsatte ender), som bevæger sig sammen: |nums[i] - nums[i+1]| for alle på hinanden følgende par. I et sorteret array opstår den mindste forskel altid mellem tilstødende elementer (fordi sorteringen samler værdier, der ligger tæt på hinanden). Det er O(n) efter sortering.
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Skabelon for to pointere fra hver sin ende
De fleste problemer med to pointere fra hver sin ende følger den samme grundstruktur. Når du mestrer denne skabelon, kan du hurtigt tilpasse den under tidspres. De vigtigste beslutninger er: (1) hvilken betingelse der flytter venstre pointer, (2) hvilken betingelse der flytter højre pointer, (3) hvad der udgør en løsning, og (4) hvordan dubletter skal håndteres. Øv dig i at omsætte disse beslutninger fra problemformuleringen, før du skriver kode.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultOptælling af gyldige par med to pointere
To pointere kan også tælle par effektivt. For problemet »tæl par med sum < target« i et sorteret array: Fastlås den venstre pointer, og brug den højre pointer til at finde det højre indeks længst til højre, som stadig er gyldigt. Alle par (left, left+1 to right) er gyldige — læg right - left til tælleren, og flyt left frem. På den måde tælles alle gyldige par i O(n) i stedet for O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Hurtigt tjek
Test din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion har du lært, at to pointere fra hver sin ende erstatter opregning af par i O(n²) med konvergens fra venstre mod højre i O(n) på sorterede arrays, at beslutningen om, hvilken pointer der skal flyttes, følger af problemets monotone egenskab — flyt den side, der aktuelt begrænser fremdriften, og at tre-sum, beholderen med mest vand, opsamling af regnvand og kontrol af palindromer alle kan reduceres til den samme grundskabelon. Næste gang ser vi på slow-fast-mønstre med to pointere.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “To pointers: modsatte ender” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “To pointers: modsatte ender”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “To pointers: modsatte ender”?
Brug venstre og højre pointere, der bevæger sig mod hinanden, til at løse sum af par i sorterede arrays, gyldigt palindrom og trapping rain water. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “To pointers: modsatte ender”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Grundlæggende arrays og in-place-operationer
- Præfiksummer og løbende totaler
- To pointers: modsatte ender
- To pointers: langsom og hurtig