Twee pointers en sliding window
Waarom slim scannen belangrijk is
Stel je een AI voor die een live videofeed bewaakt op verdachte activiteit. Het kan niet elke seconde de hele opname opnieuw bekijken - het moet een aandachtsvenster over de stream schuiven, met net genoeg context. Dat is precies wat de two pointers en sliding window patronen doen voor sequentiële data.
Beide technieken veranderen brute-force O(n²) scans in elegante O(n) doorlopen.
De Two Pointer techniek
Plaats twee referenties in een reeks en verplaats ze volgens een regel. Er zijn twee hoofdvarianten.
Convergerende pointers
Begin met één pointer aan elk uiteinde en beweeg ze naar binnen. Ideaal voor gesorteerde data.
Klassiek probleem - Pair Sum: Gegeven een gesorteerde array, vind twee getallen die optellen tot een doel.
function pairSum(arr, target):
left = 0
right = arr.length - 1
while left < right:
sum = arr[left] + arr[right]
if sum == target: return (left, right)
if sum < target: left += 1
else: right -= 1
return null
Omdat de array gesorteerd is, verhoogt het verplaatsen van left naar rechts de som, en verlaagt het verplaatsen van right naar links de som - waardoor geen enkel geldig paar wordt gemist.
Pointers in dezelfde richting
Beide pointers bewegen vooruit, maar met verschillende snelheden. Handig voor partitionering of cyclusdetectie.
Voorbeeld - Duplicaten in-place verwijderen: Een langzame pointer markeert de schrijfpositie; een snelle pointer scant vooruit.
function removeDuplicates(arr):
slow = 0
for fast in 1..arr.length - 1:
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast]
return slow + 1
Wat moet je bij de convergerende two-pointer techniek op een gesorteerde array doen wanneer de huidige som kleiner is dan het doel?
Discussion
Sign in to join the discussion