Why is a hash map the right pattern for Two Sum?

Because each index only needs one specific missing value: `target - nums[i]`. A hash map answers whether that complement already appeared, which turns repeated pair scanning into direct lookup and makes the problem linear.

Why do we check the complement before storing the current number?

That order prevents using the same element twice. If you store first, a value could match itself immediately when the target is double that number, even though only one index has been seen.

Does Two Sum still work when duplicate numbers appear?

Yes. Duplicates are fine because the map tracks indices, not just values conceptually. When the second needed copy appears, it can match the earlier stored index and return two distinct positions.

Why not sort the array first to make searching easier?

Sorting changes index positions, which breaks the original-index requirement unless you carry extra bookkeeping. For this problem, the one-pass hash map is simpler and directly preserves the correct indices.

What is the main failure mode in the Two Sum complement lookup pattern?

The usual mistake is mishandling self-pairing or returning values instead of indices. Another common issue is overcomplicating the problem with sorting or nested loops when a direct complement check already solves it.

#1

Easy

auto_awesome补数查找（哈希表）

LeetCode 题解工作台

两数之和

给定一个整数数组 nums 和一个整数目标值 target ，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。示例 1：输入： nums = [2,7,11,15…

数组哈希表

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n²) 的算法吗？

lightbulb

解题思路

方法一：哈希表

我们可以使用一个哈希表 $\textit{d}$ 来存储每个元素及其对应的索引。

遍历数组 $\textit{nums}$ ，对于当前元素 $\textit{nums}[i]$ ，我们首先判断 $\textit{target} - \textit{nums}[i]$ 是否在哈希表 $\textit{d}$ 中，如果在 $\textit{d}$ 中，说明 $\textit{target}$ 值已经找到，返回 $\textit{target} - \textit{nums}[i]$ 的索引和 $i$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i, x in enumerate(nums):
            if (y := target - x) in d:
                return [d[y], i]
            d[x] = i

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Do you recognize that Two Sum only needs a complement existence check, not comparison against every later element?
question_mark
Can you explain why checking the hash map before inserting the current value avoids reusing the same index?
question_mark
Will you justify the memory-for-speed trade-off that changes the solution from O(n^2) to O(n)?

warning

常见陷阱

外企场景

error
Inserting the current value before checking its complement can incorrectly pair an element with itself when the target is twice that value.
error
Returning the two numbers instead of their indices misses the actual output requirement of Two Sum.
error
Using a nested loop after already computing complements defeats the point of the hash map and turns this easy problem back into O(n^2).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual values instead of indices while still using the complement lookup pattern.
arrow_right_alt
Solve Two Sum II where the array is sorted and the expected follow-up uses two pointers instead of a hash map.
arrow_right_alt
Count how many distinct index pairs sum to the target, which changes duplicate handling and prevents early return after one match.

help

常见问题

外企场景

继续练习

#206 反转链表 #207 课程表