[1] 两数之和 (Two Sum)

难度：简单 | 标签：哈希表、数组

题目描述

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

解法一：暴力枚举 (Brute Force)

两层 for 循环，简单粗暴。

• 时间复杂度：
• 空间复杂度：

解法二：哈希表 (Hash Map) —— 推荐 ✅

利用 map 记录 (数值, 下标)，用空间换时间。 当我们遍历到 x 时，只需要回头看看 map 里有没有 target - x。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Key: 数值, Value: 下标
        unordered_map<int, int> map;
        
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            
            // 如果在 map 中找到了补数
            if (map.count(complement)) {
                return {map[complement], i};
            }
            
            // 没找到，把当前数存进去，等待它的“另一半”
            map[nums[i]] = i;
        }
        return {};
    }
};

易错点分析

1. 返回什么？ 题目要求返回下标，不是数值。

2. 重复元素？ 题目说“每种输入只会对应一个答案”，所以不用担心多解问题。

3. Map 类型：一定要用 unordered_map（哈希表，），别用 map（红黑树，），否则速度会慢。