leetcode 总结 01 两数之和

发表于 分类于

leetcode 总结 01 两数之和

经历了非常严重的一整年加班以后，开始想着不要继续碌碌无为了。算法这些东西，不管是需要找工作临时练手熟悉，或者是学习，总是要有的。

废话不多说。

两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      	// 两数之和 ， 一个数组 ， 一个 之和 ， 那么 总和减去当前数值 ， 就是需要查找的一个数字 。查看这个数字是否在于这个数组中
      	// 思路：用一个表用于查询第二个数值是否存在， 并且能取出第二个数值在提供数组中的位置 ，那么方便点儿就是 map了 。 key 作为数值 ，value 是索引
        // 构建一个哈希表，用于存放数据和查询 unordered_map  不需要排序
        unordered_map<int, int> hashtable;
        // 一次遍历，从头开始
        for(int i = 0; i < nums.size();i++)
        {
            //  遍历器查询缺值是否存在当前哈希表中
            auto it = hashtable.find(target - nums[i]);
            // 如果存在
            if(it != hashtable.end())
            {
                // 返回，哈希表中存放的匹配值的位置，和当前位置
                return {it->second,i};  // 注意返回值类型
            }else
            {
                // 如果不存在，那么放入当前的值和index
                hashtable[nums[i]] = i;  // 第一位是数字 ，第二位是在数组中的位置
            }
        }
        return {}; // 查不到肯定返回为空
    }
};