題目描述
Given an array of integers, return indicts 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.
輸入與輸出
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
}
};
樣例
Given nums = [2, 7, 11, 15], target = 9, because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
題解與分析
解法一（暴力）
該解法依次枚舉輸入數(shù)組中的整數(shù)，然后用線性查找方法在余下的數(shù)組中尋找是否存在能與之配對(duì)的整數(shù)。
C++ 代碼如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
// 枚舉
for (auto it = nums.begin(); it != nums.end(); ++it) {
// 線性查找（find函數(shù)定義在"algorithm"頭文件中）
auto pos = find(it + 1, nums.end(), target - *it);
if (pos != nums.end()) {
result.push_back(it - nums.begin());
result.push_back(pos - nums.begin());
break;
}
}
return result;
}
};
簡(jiǎn)單分析可得：該解法的時(shí)間復(fù)雜度為 O(n^2)放钦。
解法二
O(n^2) 的復(fù)雜度并不讓人滿意枫吧，通過(guò)觀察可以發(fā)現(xiàn)上述解法的大部分時(shí)間花費(fèi)在線性查找的過(guò)程中展运。
一個(gè)顯而易見(jiàn)的優(yōu)化是使用二分查找算法漠酿。二分查找算法需要對(duì)數(shù)組排序蒂窒，但是題目要求輸出原數(shù)組的下標(biāo)帖努，可以通過(guò)額外記錄下標(biāo)數(shù)據(jù)可以解決該問(wèn)題。
C++ 代碼如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
using pii = pair<int, int>; // 類(lèi)型別名（C++11琳疏，下同）
auto func = [](const pii& a, const pii& b) {return a.first < b.first; }; // lambda表達(dá)式
vector<int> result;
vector<pii> num;
// 記錄下標(biāo)數(shù)據(jù)
for (int i = 0; i < nums.size(); ++i)
num.push_back(make_pair(nums[i], i));
// 排序 O(nlogn)
sort(num.begin(), num.end(), func);
// 枚舉
for (auto it = num.begin(); it != num.end(); ++it) {
int key = target - it->first;
// 二分查找（lower_bound函數(shù)定義在"algorithm"頭文件中）
auto pos = lower_bound(it + 1, num.end(), make_pair(key, 0), func);
if (pos != num.end() && pos->first == key) {
// 確保下標(biāo)順序
result.push_back(it->second < pos->second ? it->second : pos->second);
result.push_back(it->second < pos->second ? pos->second : it->second);
break;
}
}
return result;
}
};
改進(jìn)后的時(shí)間復(fù)雜度為 O(nlogn)有决。
解法三
解法二的時(shí)間復(fù)雜度與運(yùn)行時(shí)間已經(jīng)令人滿意，那么能否進(jìn)一步降低時(shí)間復(fù)雜度呢空盼？
能书幕。如果使用哈希表，查找的復(fù)雜度在理想的情況下可以進(jìn)一步降低至 O(1) 揽趾。由于題目限制台汇，輸入中幾乎不會(huì)存在重復(fù)的值（唯一的例外是兩個(gè)重復(fù)值構(gòu)成答案），我們可以采用 C++ 標(biāo)準(zhǔn)庫(kù)中的 unordered_map 容器。
C++ 代碼如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
vector<int> result;
// 枚舉
for (auto it = nums.begin(); it != nums.end(); ++it) {
int key = target - *it;
// 查找
auto keyit = map.find(key);
if (keyit != map.end()) {
result.push_back(keyit->second);
result.push_back(it - nums.begin());
break;
}
map.insert(make_pair(*it, it - nums.begin()));
}
return result;
}
};
理想情況下該解法的時(shí)間復(fù)雜度為 O(n)苟呐。
