題目
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解題思路
題目的意思很簡(jiǎn)單，給你一個(gè)數(shù)組 nums[] 和一個(gè)target值杰扫，然后在該數(shù)組里找出兩個(gè)元素岸梨，使得他們加起來(lái)的和等于target值梯啤，最后返回他們的indices蚕键。
- 最粗糙的方法肯定就是暴力求解啦，不過(guò)時(shí)間復(fù)雜度為 O(n^2), 為下下策确沸。
- 接著再想到一個(gè)方法饭尝，那就是第一步先對(duì)數(shù)組排序，時(shí)間復(fù)雜度為 O(nlog(n))挨厚。 然后第二步設(shè)兩個(gè)索引 a = 0, b = n-1, 如果 nums[a] + nums[b] > target, 則 b--堡僻；如果 nums[a] + nums[b] < target, 則 a++；如果 nums[a] + nums[b] = target, 則返回 a, b 值疫剃。第二步的時(shí)間復(fù)雜度為 O(n), 所以該算法總的時(shí)間復(fù)雜度為 O(nlog(n))钉疫，該算法的代碼我沒(méi)有貼出來(lái)，因?yàn)楹苋菀拙湍軐?xiě)出來(lái)巢价。
- 第三個(gè)方法是看到討論區(qū)有人給出自己的解法牲阁，我看到挺有意思的固阁。他是利用了哈希表的方法。原理也很簡(jiǎn)單城菊，首先建立一個(gè)哈希表备燃，然后遍歷一遍數(shù)組，每次遍歷的時(shí)候凌唬，檢查在哈希表里是否存在一個(gè)元素赚爵，使得它們兩個(gè)相加等于 target 值，如果有則輸出答案法瑟，如果沒(méi)有則將該遍歷到的元素插進(jìn)哈希表中冀膝，并記錄下它的 index 值。遍歷的時(shí)間復(fù)雜度為 O(n), 每次遍歷的時(shí)候在哈希表里檢索的時(shí)間為 O(log(n)), 所以總的復(fù)雜度也為 O(nlog(n))霎挟，但是那個(gè)人說(shuō)是 O(n), 他認(rèn)為哈希表里檢索是不需要時(shí)間的窝剖，但我認(rèn)為 unordered_map 里面使用紅黑樹(shù)實(shí)現(xiàn)的，檢索是有代價(jià)的酥夭，所以我覺(jué)得復(fù)雜度為 O(nlog(n))赐纱。實(shí)現(xiàn)代碼如下：
參考代碼
一、排序方法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int, int> hash, temp;
//map<int, int> hash;
for(int i=0;i<nums.size() ;i++){
if(hash.find(nums[i])==hash.end())
hash[nums[i]]=i;
else
temp[nums[i]]=i;
}
sort(nums.begin() ,nums.end());
int i=0, j=nums.size()-1;
while(i<j){
if(nums[i]+nums[j]==target){
if(nums[i]==nums[j]){
ans.push_back(hash[nums[i]]);
ans.push_back(temp[nums[i]]);
}
else{
ans.push_back(hash[nums[i]]);
ans.push_back(hash[nums[j]]);
}
break;
}
else if(nums[i]+nums[j]<target)
i++;
else
j--;
}
return ans;
}
};
二熬北、哈希方法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//Key is the number and value is its index in the vector.
unordered_map<int, int> hash;
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
int numberToFind = target - nums[i];
//if numberToFind is found in map, return them
if (hash.find(numberToFind) != hash.end()) {
//+1 because indices are NOT zero based
result.push_back(hash[numberToFind] );
result.push_back(i );
return result;
}
//number was not found. Put it in the map.
hash[nums[i]] = i;
}
return result;
}
};
反思與總結(jié)
有人會(huì)認(rèn)為這題那么簡(jiǎn)單疙描，為什么還要記錄下來(lái)。我認(rèn)為這題雖簡(jiǎn)單讶隐，但對(duì)我還是有一定啟發(fā)的起胰。因?yàn)閷?duì) unordered_map, map 等這些數(shù)據(jù)結(jié)構(gòu)，雖然我了解他們的原理和實(shí)現(xiàn)巫延，但往往在實(shí)際中很少會(huì)想起使用他們效五，從而導(dǎo)致自己的算法臃腫低效，所以我們應(yīng)該在實(shí)戰(zhàn)中多多利用這些封裝性強(qiáng)炉峰，效率高效并且使用簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)畏妖，往往他們會(huì)出奇效~
