双指针与滑动窗口
Why Scanning Smartly Matters
Imagine an AI monitoring a live video feed for suspicious activity. It cannot rewatch the entire recording every second - it needs to slide a window of attention across the stream, keeping track of just enough context. That is exactly what the two pointers and sliding window patterns do for sequential data.
Both techniques turn brute-force O(n²) scans into elegant O(n) passes.
The Two Pointer Technique
Place two references into a sequence and move them according to a rule. There are two main flavours.
Converging Pointers
Start one pointer at each end and move them inward. Perfect for sorted data.
Classic problem - Pair Sum: Given a sorted array, find two numbers that add to a target.
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
Because the array is sorted, moving left right increases the sum, and moving right left decreases it - guaranteeing we never miss a valid pair.
Same-Direction Pointers
Both pointers move forward, but at different speeds. Useful for partitioning or cycle detection.
Example - Remove duplicates in-place: A slow pointer marks the write position; a fast pointer scans ahead.
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
In the converging two-pointer technique on a sorted array, what should you do when the current sum is less than the target?
Discussion
Sign in to join the discussion