Two Pointers

The Idea

Keep one index at each end and move them toward each other based on what you see. Every step rules out a whole group of pairs at once. Brute force checks every pair in O(n²); two pointers does the same job in O(n).

Real-World Example

Two people search a long bookshelf for a matching pair of volumes, one starting at each end and walking inward. They meet in the middle having covered the shelf exactly once, rather than one person re-walking it for every single book.

The Code

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return (left, right)
        if total < target:
            left += 1        # need a bigger sum
        else:
            right -= 1       # need a smaller sum
    return None

# two_sum_sorted([1, 3, 4, 8, 11], 11) -> (1, 3)

nums = [2, 5, 9]
l, r = 0, 2
while l < r:
  print(nums[l] + nums[r])
  l += 1
  r -= 1