題目鏈接：
題目描述：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target栓票，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)伐谈，并返回他們的數(shù)組下標(biāo)抵恋。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是外驱，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素育灸。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
算法：
題目非常簡(jiǎn)單。要在數(shù)組中找到兩個(gè)整數(shù)之和為target昵宇，那么只需要把數(shù)組雙層遍歷一遍磅崭，找出所有可能的組合即可。由于每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案瓦哎，因此找到之后就可以直接輸出砸喻。對(duì)應(yīng)的時(shí)間復(fù)雜度是
，空間復(fù)雜度是
蒋譬。
但是割岛，
即可惠爽。可以考慮先將其進(jìn)行排序瞬哼，然后尋找元素婚肆。用快排的速度為
，然后用二分查找的速度也為
结胀。
當(dāng)然對(duì)于有序的列表來說赞咙，可以用首尾遞進(jìn)進(jìn)行查找。先取nums[0] 和 nums[n - 1]糟港，如果它們相加大于k人弓，則將取nums[0] 與 nums[n - 2]；如果小于k着逐，則取nums[1] 和 nums[n - 1]再進(jìn)行比較。這樣只需要遍歷一遍數(shù)組意蛀，時(shí)間復(fù)雜度為前面的算法建立了一個(gè)hash表來儲(chǔ)存下標(biāo)秀姐。事實(shí)上，我們可以用儲(chǔ)存的下標(biāo)來表示該數(shù)有沒有出現(xiàn)過若贮，并且在每次存入一個(gè)數(shù)的時(shí)候省有，判斷
代碼：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[i] + nums[j] == target)
return {i, j};
}
}
return {};
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map <int, int> label;
for (int i = 0; i < nums.size(); ++i) {
// Some values can be same. For instance, { [3, 3], 6 }
// if we assign value without judge, the result will be (1, 1)
if (label.count(nums[i]) && 2 * nums[i] == target)
return { label[nums[i]], i };
else
label[nums[i]] = i;
}
sort(nums.begin(), nums.end());
int head = 0, tail = nums.size() - 1;
while (head < tail) {
if (nums[head] + nums[tail] == target)
return { label[nums[head]], label[nums[tail]] };
if (nums[head] + nums[tail] < target)
head++;
if (nums[head] + nums[tail] > target)
tail--;
}
return {};
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map <int, int> label;
for (int i = 0; i < nums.size(); ++i) {
// The number we found can't be itself.
// For example, { [3, 2, 4]舷蟀，6} 恤磷。Of course 3+3 is the result, but it's wrong.
if (label.count(target - nums[i]) && label[target - nums[i]] != i)
return { label[target - nums[i]], i };
// We should assign value after judge it.
// For example, { [3, 3]，6 }, if we assign value before judge, we will get nothing.
label[nums[i]] = i;
}
return {};
}
};
