Två pekare: motsatta ändar
Använd vänster- och högerpekare som rör sig mot varandra för att lösa summor av par i sorterade arrayer, giltiga palindrom och trapping rain water.
Två pekare: motsatta ändar är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 3 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Idén med två pekare
Tvåpekartekniken använder två indexvariabler som rör sig mot varandra (eller i samma riktning) för att minska behovet av nästlade loopar. I stället för att kontrollera varje par på O(n²)-tid gör du framsteg vid varje jämförelse och blir klar på O(n)-tid. Arrayen måste nästan alltid vara sorterad först, eftersom sorteringen gör det möjligt att avgöra åt vilket håll varje pekare ska flyttas utifrån om den aktuella parsumman är för stor eller för liten.
# 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 []Tvåsumma i en sorterad array
I en sorterad array placerar du en pekare längst till vänster (det minsta värdet) och en längst till höger (det största värdet). Om summan är för liten flyttar du vänsterpekaren åt höger för att öka den. Om summan är för stor flyttar du högerpekaren åt vänster för att minska den. Vid varje iteration flyttas minst en pekare, så loopen körs högst n gånger: totalt O(n)-tid efter sorteringen. Det är viktigt att varje förflyttning är bevisligen korrekt tack vare sorteringsordningen.
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]Kontrollera giltig palindrom
En sträng är en palindrom om den läses likadant framifrån och bakifrån. Använd två pekare som börjar i varsin ände och rör sig inåt: jämför tecken, hoppa över icke-alfanumeriska tecken och avsluta när pekarna korsar varandra. Detta tar O(n)-tid och O(1) extra utrymme — betydligt renare än att vända på strängen och jämföra den, vilket allokerar O(n) extra minne.
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-summa: sortera + två pekare
Tre-summa handlar om att hitta alla unika tripplar vars summa är noll. Sortera arrayen, fixera sedan varje element nums[i] och kör en sökning med två pekare i den återstående delarrayen efter ett par vars summa är -nums[i]. Hoppa över dubbletter av både det fixerade elementet och det hittade paret för att undvika upprepade tripplar. Total tid: O(n²) efter sortering på O(n log n)-tid.
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]]Behållare med mest vatten
Givet höjderna för lodräta linjer ska du hitta två linjer som bildar en behållare med så mycket vatten som möjligt. Area = min(height[left], height[right]) × (right - left). Flytta girigt pekaren vid den kortare linjen inåt: om du flyttar den högre linjen minskar bredden utan att höjdbegränsningen kan öka. Detta giriga val är bevisligen optimalt och ger 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])) # 49Kvadrera en sorterad array
Kvadrera varje element i en sorterad array, som kan innehålla negativa tal, och returnera resultatet i sorterad ordning. Negativa värden ger stora kvadrater; positiva värden ger mindre kvadrater närmare mitten. Placera två pekare i varsin ände och fyll resultatarrayen från höger till vänster (från störst till minst). Detta ger O(n)-tid och O(n)-utrymme för resultatet — mycket bättre än att först kvadrera och sedan sortera 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]Fånga regnvatten
Vattnet som fångas vid index i är lika med min(max_left, max_right) - height[i]. Med tvåpekarmetoden upprätthåller du de löpande värdena max_left och max_right. När max_left < max_right är vänstersidan flaskhalsen — bearbeta vänsterpekaren. Annars bearbetar du högerpekaren. Då behövs inga separata arrayer för största värdet till vänster och höger, vilket ger O(1) extra utrymme.
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])) # 6Varför den giriga pekarförflyttningen fungerar
En vanlig följdfråga i intervjuer är: varför är det säkert att kasta bort den mindre pekaren? En kort bevisidé för problemet med behållaren som rymmer mest vatten: anta att height[left] < height[right]. Varje par (left, j) för j < right ger en area ≤ height[left] × (j-left) < height[left] × (right-left) ≤ den aktuella arean. Inget par som börjar vid 'left' och har ett högerindex mindre än 'right' kan alltså överträffa den aktuella arean. Vi kan tryggt hoppa över dem genom att flytta left framåt.
# 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 minsta skillnad i sorterad array
Hitta talparet i en sorterad array som har den minsta absoluta skillnaden. Använd två intilliggande pekare (inte pekare från motsatta ändar) som skannar tillsammans: |nums[i] - nums[i+1]| för alla på varandra följande par. Den minsta skillnaden i en sorterad array uppstår alltid mellan intilliggande element, eftersom sorteringen samlar närliggande värden. Detta är O(n) efter sorteringen.
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) 1Mall för två pekare från motsatta ändar
De flesta problem med två pekare från motsatta ändar följer samma grundstruktur. När ni behärskar den här mallen kan ni snabbt anpassa den under tidspress. De viktigaste besluten är: (1) vilket villkor som flyttar vänsterpekaren, (2) vilket villkor som flyttar högerpekaren, (3) vad som utgör en lösning och (4) hur dubbletter ska hanteras. Öva på att formulera dessa beslut utifrån problemformuleringen innan ni skriver kod.
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 resultRäkna giltiga par med två pekare
Två pekare kan också användas för att räkna par effektivt. För problemet ”räkna par med summa < target” i en sorterad array: fixera vänsterpekaren och använd högerpekaren för att hitta det högsta giltiga högerindexet. Alla par (left, left+1 till right) är giltiga — lägg till right - left till antalet och flytta vänsterpekaren framåt. Då räknas alla giltiga par i O(n) i stället för 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) -> 4Snabbtest
Testa er förståelse av begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde ni er att två pekare från motsatta ändar ersätter uppräkning av par i O(n²) med konvergens från vänster och höger i O(n) på sorterade arrayer, att beslutet om vilken pekare som ska flyttas följer av problemets monotona egenskap — flytta den sida som för närvarande begränsar framstegen och att three-sum, container-with-most-water, trapping rain water och verifiering av palindrom alla kan reduceras till samma grundläggande mall. Härnäst utforskar vi mönster med långsamma och snabba tvåpekare.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Två pekare: motsatta ändar” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Två pekare: motsatta ändar”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Två pekare: motsatta ändar”?
Använd vänster- och högerpekare som rör sig mot varandra för att lösa summor av par i sorterade arrayer, giltiga palindrom och trapping rain water. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Två pekare: motsatta ändar”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Grunderna i arrayer och in-place-operationer
- Prefixsummor och löpande totalsummor
- Två pekare: motsatta ändar
- Två pekare: långsam och snabb