1. 两数之和

题目

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法一 – 暴力求解

两层for循环

方法二 – 两遍哈希表

步骤：

1. 遍历数组，将数据中的元素放入到哈希表中
2. 遍历数组，从哈希表中寻找是否有相加和为target的数据

注意点：

第二次遍历数组的时候，第一次遇到相加和为target的数据的时候，就应该退出循环，如果不退出，将会有两个结果，比如第一次匹配到了1，2，那么还会匹配一次2，1

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> arr;
        unordered_map<int,int> nums_map;
        for (int i = 0; i < nums.size(); ++i) {
            nums_map.insert(pair<int,int>(nums[i],i));
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (nums_map.find(target - nums[i]) != nums_map.end() && nums_map.find(target - nums[i])->second != i) {
                arr.push_back(i);
                arr.push_back(nums_map.find(target - nums[i])->second);
                break;
            }
        }
        return arr;
    }
};

方法三 – 一遍哈希表

思路

方法二中需要先把数据全部放入到哈希表中，然后查找
方法三是让数据的时候一边放一边查找，即使从先查的nums中找不到后面的数据，但是后面的数据在查找的时候，前面的数据已经放在了哈希表中了

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> arr;

        unordered_map<int,int> nums_map;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums_map.find(target - nums[i]) != nums_map.end()) {
                arr.push_back(i);
                arr.push_back(nums_map.find(target - nums[i])->second);
            } else {
                nums_map.insert(pair<int,int>(nums[i],i));
            }
        }
        return arr;
    }
};