NeetCode #199LC-167MediumTwo PointersNC 150NC 250
← Back to All Problems#199 · #167 · Two Sum II - Input Array Is Sorted(两数之和 II - 输入有序数组)
📌 Problem Statement & Constraints
Given a 1-indexed array of integers
numbers sorted in non-decreasing order, find two numbers that add up to a target and return their 1-indexed positions. Exactly one solution exists and you may not use the same element twice. Constraints: 2 <= numbers.length <= 3 * 10^4, -1000 <= numbers[i] <= 1000, -1000 <= target <= 1000.💡 Core Algorithmic Approaches
- The sortedness is the key resource: with two pointers at the ends, the sum tells you which pointer to move.
- If the current sum is too small, the only way to increase it is to move the left pointer right.
- If the sum is too large, move the right pointer left.
- This is O(n) time with O(1) space -- better than the hash-map solution, which is O(n) space.
💻 Benchmark Python3 Implementation
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i, j = 0, len(numbers) - 1
while i < j:
s = numbers[i] + numbers[j]
if s == target:
return [i + 1, j + 1] # 1-indexed output
if s < target:
i += 1 # need a larger sum
else:
j -= 1 # need a smaller sum
return []⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each pointer moves at most n steps, so the total is O(n).
💾 Space Complexity
O(1): two indices.
⚠️ Interview Pitfalls & Follow-ups
- Returning 0-indexed positions: the problem is explicitly 1-indexed, so
+1is required. - Using a hash map: correct and O(n) time, but O(n) space. The sorted input makes the two-pointer approach strictly better.
- Moving both pointers on a mismatch: only one should move, otherwise the invariant is broken.
- Assuming the array is strictly increasing: the problem says non-decreasing, so duplicates are possible -- but the two-pointer logic handles them fine.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.