Two Sum（两数之和）

题目 / Problem

中文： 你被给定一个整数数组 nums 和一个整数 target，请返回数组中两个数之和等于 target 的元素下标。

English: You are given an array of integers nums and an integer target. Return the indices of the two numbers such that they add up to target.

要求 / Requirements：

每个输入只存在一个有效答案。
Each input has exactly one solution.
同一个元素不能使用两次。
You may not use the same element twice.
返回下标的顺序不限。
You can return the answer in any order.

示例 / Examples

Example 1

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
解释：因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]。

Example 2

Input:  nums = [3, 2, 4], target = 6
Output: [1, 2]

Example 3

Input:  nums = [3, 3], target = 6
Output: [0, 1]

约束 / Constraints

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
只存在一个有效答案。
Only one valid answer exists.

进阶 / Follow-up

能否设计一个时间复杂度低于 O(n²) 的算法？
Can you come up with an algorithm that is less than O(n²) time complexity?

解题思路：哈希表 / Approach: Hash Map

遍历数组时，当前元素为 nums[i]，需要寻找的另一个数是：
While iterating through the array, the other number we need is:

complement = target - nums[i]

使用哈希表保存已经遍历过的元素及其下标。
Use a hash map to store the numbers that have already been visited and their indices.

计算当前元素所需的补数 complement。
Calculate the complement required by the current number.
如果哈希表中存在补数，直接返回补数下标和当前下标。
If the complement exists in the hash map, return its index and the current index.
如果不存在，将当前元素及其下标加入哈希表。
Otherwise, add the current number and its index to the hash map.
查找必须先于插入，避免把同一个元素使用两次。
Look up the complement before inserting the current number, so the same element is not used twice.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  // key: 数值，value: 下标
  // key: number, value: index
  const indexMap = new Map();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (indexMap.has(complement)) {
      return [indexMap.get(complement), i];
    }

    indexMap.set(nums[i], i);
  }

  // 题目保证一定有解，这里仅作为兜底返回值。
  // The problem guarantees a solution; this is only a fallback.
  return [];
}

执行过程 / Walkthrough

以 nums = [2, 7, 11, 15]、target = 9 为例：
For nums = [2, 7, 11, 15] and target = 9:

下标 Index `i`	当前值 Current value	补数 Complement	哈希表 Hash map	结果 Result
0	2	7	`{2: 0}`	未找到 / Not found
1	7	2	`{2: 0}` 中存在 2 / 2 exists	`[0, 1]`

复杂度 / Complexity

时间复杂度：O(n)，数组只遍历一次。
Time: O(n), because the array is traversed once.
空间复杂度：O(n)，哈希表最多保存 n 个元素。
Space: O(n), because the hash map can store up to n elements.

暴力解法对比 / Brute-Force Comparison

枚举每一对元素并判断其和是否等于 target。
Check every pair of elements to determine whether their sum equals target.

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }

  return [];
}

时间复杂度：O(n²)。
Time: O(n²).
空间复杂度：O(1)（不考虑返回结果）。
Space: O(1) (excluding the returned result).

哈希表解法将时间复杂度优化到了 O(n)。
The hash-map solution improves the time complexity to O(n).

易错点 / Common Pitfalls

返回的是下标，不是两个数本身。
Return indices, not the two numbers themselves.
不能在查找补数之前就插入当前元素。
Do not insert the current element before looking up its complement.
nums = [3, 3] 时，需要保留两个不同下标。
For nums = [3, 3], use the two different indices.
数组元素和 target 可能为负数，补数计算仍然适用。
Array elements and target may be negative; the complement calculation still works.

Two Sum