题目：

1. 两数之和

难度简单16479收藏分享切换为英文接收动态反馈

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 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 <= 104

• -109 <= nums[i] <= 109

• -109 <= target <= 109

• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

第一种对法：

暴力解法O(n^2)

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> s;

        int flag = 0;

        for(int i=0;i<nums.size();i++){

            for(int j=0;j<nums.size();j++){

                if(nums[i]+nums[j]==target&&i!=j){

                    s.push_back(i);s.push_back(j);

                    flag = 1;

                    break;

                }

            }

            if(flag)break;

        }

        return s;

    }

};

第二种对法：

哈希表：

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        unordered_map<int,int> map;

        for(int i=0;i<nums.size();i++){

            auto iner = map.find(target-nums[i]);

            if(iner!=map.end())return {iner->second,i};

            map.insert(pair<int,int>(nums[i],i));

        }

        return {};

    }

};

如何想到用哈希表？

本题可以利用正在遍历的nums元素（1）和target求出另一个nums元素（2）的值，但这个

nums元素（2）的值不知道是否真的存在，这时就可以回顾刚才遍历过的元素来判断这个nums元素（2）是否存在，在这里就是要判断一个元素是否被遍历过，在这种情况下就要使用哈希表，我们要使用的哈希表是c++中的unorder_map(底层原理是哈希表)，key要放用于寻找的值，此题中我们要寻找nums元素 (2) ，所以key就用来放nums元素 (2) ，value就用来放nums元素（2）的位置值。

注意：

返回vector<int>的方法：{要返回的数}