題目：

1. 兩數(shù)之和

難度簡單16479收藏分享切換為英文接收動態(tài)反饋

給定一個整數(shù)數(shù)組?nums?和一個整數(shù)目標(biāo)值?target，請你在該數(shù)組中找出?和為目標(biāo)值?target? 的那?兩個?整數(shù)，并返回它們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。

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

?

示例 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

• 只會存在一個有效答案

進(jìn)階：你可以想出一個時間復(fù)雜度小于?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>的方法：{要返回的數(shù)}