THE LIST IS SORTED. PUT ONE CURSOR AT EACH END AND PINCH INWARD. A SUM TOO BIG MEANS DROP THE RIGHT, TOO SMALL MEANS RAISE THE LEFT.
SORTED MEANS THE ENDS ARE THE EXTREMES. MOVING A CURSOR INWARD ALWAYS SHRINKS THE SUM, SO EACH STEP RULES OUT EXACTLY ONE END.
ONE PASS, TWO CURSORS. BLUE L CLIMBS FROM THE LEFT, PINK R DROPS FROM THE RIGHT. THE GOLD PAIR IS THE ANSWER.
1def two_sum(numbers, target):2 l = 03 r = len(numbers) - 14 while l < r:5 if numbers[l] + numbers[r] == target:6 return [l + 1, r + 1]7 elif numbers[l] + numbers[r] > target:8 r -= 19 else:10 l += 1
EACH STEP RETIRES ONE END, SO THE TWO CURSORS MEET AFTER AT MOST N MOVES.
JUST TWO INDICES. THE SORTED INPUT IS WHAT LETS US DROP TWO SUM'S HASH MAP.