1.?兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)嗤军。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。
示例:
給定 nums = [2, 7, 11, 15], target = 9因?yàn)?nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]
解法一：暴力解法匙奴，復(fù)雜度o（n平方）
解法二，排序后妄荔，使用雙索引對(duì)撞（參考letcode167 two sum ）
復(fù)雜度O（nlogn）+O(n)=O(nlogn)
解法3查找表泼菌。將所有元素放入查找表，之后對(duì)于每一個(gè)元素a啦租，查找target-a是否存在
class Solution {
public:
? ? vector<int> twoSum(vector<int>& nums, int target) {
? ? ? ? unordered_map<int,int> record;
? ? ? ? for(int i=0;i<nums.size();i++)
? ? ? ? {
? ? ? ? ? ? int complement=target-nums[i];
? ? ? ? ? ? if(record.find(complement)!=record.end())
? ? ? ? ? ? {? int res[2]={i,record[complement]};
? ? ? ? ? ? ? return vector<int>(res,res+2);
? ? ? ? }
? ? ? ? record[nums[i]]=i;
? ? }
? ? throw invalid_argument("the input has no solution");
? ? }
};
時(shí)間復(fù)雜度O(N)空間復(fù)雜度O(N)哗伯；
類似題目15號(hào)3sum 18題4sum16題3sum closest
