Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

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

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [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 <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

Only one valid answer exists.

My Solution

我最开始的想法非常简单。使用双层嵌套循环暴力枚举，逐个检查所有可能的元素对(nums[i], nums[j])。

外层循环执行n-1次，内层循环对于每个i最多执行n-i-1次。
总操作次数约为n²/2，时间复杂度为O(n²)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// Runtime: 30ms
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i+1; j<n; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

The Best Solution

遍历数组，每次遍历时，计算一下当前需要的另一个加数，并检查当前哈希表内是否存在。如果不存在，就把当前的num[i]作为键，i作为值插入到哈希表。这样等到下次需要用到这个值时，直接通过键就可以获得索引并返回。

该算法采用哈希表（unordered_map） 实现，核心思想是通过空间换时间，将时间复杂度优化到线性级别。

利用哈希表的快速查找特性（平均 O(1) 时间复杂度），避免暴力枚举的双层循环。核心逻辑：对于数组中的每个元素 nums[i]，计算它与目标值的差值 complement = target - nums[i]。

如果 complement 已在哈希表中，说明之前遍历过的元素中存在与 nums[i] 配对的元素，直接返回两者的索引；否则，将当前元素存入哈希表，继续遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.count(complement)) {
                return {numMap[complement], i};
            }
            numMap[nums[i]] = i;
        }

        return {};
    }
};