两数之和：哈希表查找补数

题目要求在数组中找到两个不同下标，使其元素之和等于 target。关键是把“寻找另一个数”转换为“查询补数”。

思路#

先把每个数值与其下标写入映射；随后遍历数组，查询补数 target - nums[i] 是否存在，且其下标不能与当前下标相同。

当前代码的处理方式
这份实现采用“先建表、后查询”的两次遍历；m[k] != i 用于排除同一个元素被重复使用的情况。

1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int target) {
4
        int n = nums.size();
5

6
        map<int, int> m;
7
        vector<int> ans;
8

9
        for(int i = 0; i < n; i ++ ) m[nums[i]] = i;
10

11
        for(int i = 0; i < n; i ++ ) {
12
            auto x = nums[i];
13
            int k = target - x;
14
            if(m.count(k) && m[k] != i) {
15
                ans.push_back(i);
16
                ans.push_back(m[k]);
17
                break;
18
            }
19
        }
20

21
        return ans;
22
    }
23
};

复杂度与边界#

时间复杂度： $O(n)$ ，每次哈希查询均摊为常数时间。
空间复杂度： $O(n)$ 。
数组存在重复元素时仍然有效；题目保证唯一答案时可直接返回。