1. 兩數(shù)之和

難度簡(jiǎn)單16762

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

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

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

?

示例 1：

輸入：nums = [2,7,11,15], target = 9輸出：[0,1]解釋：因?yàn)?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

• 只會(huì)存在一個(gè)有效答案

?

進(jìn)階：你可以想出一個(gè)時(shí)間復(fù)雜度小于?O(n2)?的算法嗎？

第一種對(duì)法：

暴力解法：時(shí)間復(fù)雜度O(n^2)

直接兩個(gè)for無腦解出答案

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;

????}

};

第二種對(duì)法：

利用哈希表，時(shí)間復(fù)雜度為O(n)

思路：遍歷一遍數(shù)組，邊遍歷一邊尋找在前面是否有遍歷過與該值相加與target相等的元素。

尋找一個(gè)元素是否在一個(gè)數(shù)組中出現(xiàn)：哈希表

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;

????}

};