题解 | 两数之和

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // 使用unordered_map作为哈希表，存储数字和对应的索引
        unordered_map<int, int> hashMap;
        
        // 遍历数组
        for (int i = 0; i < numbers.size(); i++) {
            // 计算需要的补数
            int complement = target - numbers[i];
            
            // 如果补数在哈希表中，说明找到了解
            if (hashMap.find(complement) != hashMap.end()) {
                // 返回下标（从1开始），确保升序排列
                return {hashMap[complement] + 1, i + 1};
            }
            
            // 将当前数字和索引存入哈希表
            hashMap[numbers[i]] = i;
        }
        
        // 根据题目保证，一定会找到解，所以这里不会执行到
        return {};
    }
};

算法详解
1.核心思路
使用哈希表（unordered_map）来存储每个数字及其对应的索引，这样可以在O(1)时间内查找补数是否存在。

2.执行步骤
初始化哈希表：用于存储数字和索引的映射关系
遍历数组：对于每个元素 numbers[i]
计算补数 complement = target - numbers[i]
检查补数是否在哈希表中
如果存在，返回两个索引（从1开始）
如果不存在，将当前数字和索引存入哈希表

3.复杂度分析
时间复杂度：O(n)，只需遍历数组一次
空间复杂度：O(n)，最坏情况下需要存储n个元素到哈希表

4.关键点说明
使用 unordered_map 而不是 map，因为前者平均O(1)的查找时间更优
hashMap.find(complement) != hashMap.end() 检查补数是否存在
返回时索引+1，因为题目要求下标从1开始
由于哈希表中存储的是之前遍历过的元素索引，所以返回时自然满足升序要求