Two Pointers Pointers from both ends
153. Two Sum II - Input Array Is Sorted
You are given an array of integers nums sorted in non-decreasing order, and an integer target. Exactly one
pair of elements in nums has a sum equal to target. Return the positions of those two elements as [i, j],
with i < j.
Non-decreasing means that each element is greater than or equal to the one before it, so a value can appear more than once. The two elements must be at different positions, and positions are counted from 0.
Example 1
Input: nums = [-4, 1, 3, 6, 9, 15], target = 12
[2,4]Explanation: 3 + 9 = 12, and 3 is at position 2 and 9 at position 4. The 6 is half of 12, but the array holds only one 6, and one element cannot be both halves of the pair.
Example 2
Input: nums = [-7, 2, 2, 2, 9, 10], target = 3
[0,5]Explanation: −7 is the first element and 10 is the last, and they add up to 3. The value 2 appears three times, but the array has no 1 to go with it.
Example 3
Input: nums = [-11, -6, -6, 1, 3], target = -12
[1,2]Explanation: The pair is the two copies of −6, at positions 1 and 2. A value that repeats can form the pair, because each copy sits at its own position.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
2 ≤ nums.length ≤ 105-2·109 ≤ nums[i] ≤ 2·109-2·109 ≤ target ≤ 2·109numsis sorted in non-decreasing order.- Exactly one pair of positions
i < jhasnums[i] + nums[j] = target.
Clarifying questions
What you would ask an interviewer before writing any code.