💬 Discord
Sign In
NeetCode #36LC-1EasyArrays & HashingBlind 75NC 150NC 250
← Back to All Problems

#36 · #1 · Two Sum(两数之和)

📌 Problem Statement & Constraints

Given an array of integers nums and an integer target, return the indices [i, j] such that nums[i] + nums[j] == target, with i != j. Exactly one solution is guaranteed, and you may not use the same element twice. Constraints: 2 <= nums.length <= 10^4, -10^9 <= nums[i], target <= 10^9.

💡 Core Algorithmic Approaches

  1. The brute-force double loop is O(n^2). The key observation is that once you fix the current element x, the partner you need is fully determined: target - x.
  2. Keep a hash map from value to index for the elements already visited.
  3. For each x at index i, check whether target - x is already in the map. If it is, its stored index j < i forms a valid answer [j, i].
  4. Only insert x after the lookup. Inserting first would let an element pair with itself when 2 * nums[i] == target.

💻 Benchmark Python3 Implementation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}                      # value -> index
        for i, x in enumerate(nums):
            need = target - x
            if need in seen:           # lookup BEFORE insert -> no self-pairing
                return [seen[need], i]
            seen[x] = i
        return []                      # unreachable per problem guarantee

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass with O(1) average hash lookups and insertions. The O(n^2) brute force is the only realistic alternative.
💾 Space Complexity
O(n) for the hash map. Note that the map stores at most one index per distinct value, so a duplicate value overwrites the earlier index -- which is fine, because the earlier index would already have produced an answer if it could.

⚠️ Interview Pitfalls & Follow-ups

  • Inserting before looking up: nums = [3, 3], target = 6 would return [0, 0], reusing one element twice.
  • Sorting plus two pointers: it finds the values in O(n log n), but you must return original indices, so you would have to carry index-value pairs and handle duplicates carefully.
  • Assuming the array is sorted: it is not; the hash map makes order irrelevant.
  • Worrying about integer overflow: values reach 1e9, so target - x can be about 2e9 -- harmless in Python, but a real concern in Java/C++ with 32-bit ints.