【Leetcode Daily】1两数之和

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整型数组和目标值，从数组中找出两个值之和正好为目标值的下标，题目保证数组不重复，且必有唯一答案。要求两个下标不能相同。

思路分享

• 暴力法就是直接上两层循环，本题的目标是把时间复杂度降到O(n)。

• 下面就是灵神题解中介绍枚举方法，一个循环遍历一个值，每次遍历就在哈希表查找剩余另一个的值，没找到就把当前值和对应下标存哈希表。

  https://leetcode.cn/problems/two-sum/solutions/2326193/dong-hua-cong-liang-shu-zhi-he-zhong-wo-0yvmj/

• 注意，顺序很重要，不能先放哈希表再查找，不然就会找到相同下标的情况。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> rec;
        for (int i = 0; i < nums.size(); i++) {
            const auto &it = rec.find(target-nums[i]);
            if (it!=rec.end()) {
                return {it->second, i};
            }
            rec[nums[i]] = i;
        }
        return {};
    }
};