leetCode 1. 两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

---

思考

需要在一个数组中找到两个数的和等于一个特定的值

首先想到两层遍历暴力解法

for (i = 0; i < length; i++)
    for (j = i + 1; j < length; j++)
        if (nums[i] + nums[j] == target) 
            return [i, j];

两层遍历的时间复杂度是O(n*n)
然后就能想到用哈希表来用空间换取时间
建立一个哈希表，时间复杂度就可以降低到O(n)
这里有个比较关键的点，就是遍历的时候，需要注意是不是同一个元素

构建哈希表
map<int, int> hashMap
for (i = 0; i < length; i++)
    map.put(nums[i], i);

查找
for (i = 0; i < length; i++)
    diff = target - nums[i];
    if (map.found(diff) && hashMap[diff] != i)
        return [i, hashMap[diff]];

写到这里，似乎这题已经被完美解决了，但是仔细想想，构建哈希表和查找是不是可以在一个遍历中完成呢，虽然在一开始查找遍历的时候哈希表是空的，但是这并不会影响最后我们想要的结果，因为在向后遍历的时候，哈希表的元素也在一直变多，把插入哈希表的操作放在查找到后面，这样还可以避免掉是同一个元素的问题

for (i = 0; i < length; i++)
    diff = target - nums[i];
    if (map.found(diff))
        return [i, hashMap[diff]];
    map.put(nums[i], i);

---

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> hashMap;
        for (int i=0; i<nums.size(); i++) {
            int diffValue = target - nums.at(i);
            if (hashMap(diffValue) != hashMap()) {
                return {hashMap[diffValue], i};
                break;
            } else {
                hashMap(pair<int, int>(nums.at(i), i));
            }
        }
    } 
};

---

基础知识

哈希表（Hash table）