描述
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].
思路一
由于數(shù)組中只有唯一一對符合目標的索引播玖，故我們可以采用雙重循環(huán)解決象颖，時間復(fù)雜度
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
for(int i = 0;i<nums.size()-1;i++)
{
for(int j = i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]==target)
{
ret.push_back(i);
ret.push_back(j);
break;
}
}
}
return ret;
}
};
思路二
我們采用map數(shù)據(jù)結(jié)構(gòu)，定義當前索引為i赵讯，那么當前元素為nums[i]斑响。我們試圖在map里邊找一個元素numTofind（numTofind = target - nums[i])傻谁，找到了返回map[numTofind]值即可葫慎「诠常可以做以下思考，當找到滿足 尘盼？+ 憨愉？= target 的第一個元素的時候呜魄，他是被放進map中去的，當找到第二個元素的時候莱衩，才把第一個元素取出。連同第二個元素放入到vector中娇澎。時間復(fù)雜度為
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hash;
vector<int> res;
int numTofind;
for(int i=0;i<nums.size();i++)
{
numTofind = target - nums[i];
//hash中找到了唯一一對中的前一個元素笨蚁，兩個元素分別進入vector
if(hash.find(numTofind)!=hash.end())
{
res.push_back(hash[numTofind]);
res.push_back(i);
break;
}
//hash沒有找到，保存到hash中
hash[nums[i]] = i;
}
return res;
}
};
不好理解運行過程的話趟庄，手動模擬一下樣例即可括细。
