Two sum in a sorted list
You get a list of integers nums, sorted from smallest to largest, and an integer target. Exactly one pair of different positions holds two numbers that add up to target. Return those two positions as a list [i, j] with i < j.
Aim for O(1) extra space: the sorted order is enough, so you need no dict or set. Positions count from 0, as Python indexes do (LeetCode's version counts them from 1).
nums = [1, 4, 5, 7, 12], target = 9Output[1, 2]nums[1] + nums[2] is 4 + 5 = 9. No other pair makes 9.
nums = [-4, -1, 0, 3, 10], target = 6Output[0, 4]-4 + 10 = 6: the pair can be the two ends.
nums = [5, 5, 8], target = 10Output[0, 1]Equal values at two different positions are a valid pair.
2 ≤ len(nums) ≤ 3 × 104
-109 ≤ nums[i], target ≤ 109
numsis sorted from smallest to largest; equal neighbors are allowed.Exactly one valid pair exists.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.