⚡Flashcard Drill➔
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

  1. The sortedness is the key resource: with two pointers at the ends, the sum tells you which pointer to move.
  2. If the current sum is too small, the only way to increase it is to move the left pointer right.
  3. If the sum is too large, move the right pointer left.
  4. 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 +1 is 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.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems