給一個(gè)整數(shù)數(shù)組，找到兩個(gè)數(shù)使得他們的和等于一個(gè)給定的數(shù) target铭段。
你需要實(shí)現(xiàn)的函數(shù)twoSum需要返回這兩個(gè)數(shù)的下標(biāo), 并且第一個(gè)下標(biāo)小于第二個(gè)下標(biāo)。注意這里下標(biāo)的范圍是 1 到 n，不是以 0 開頭玄叠。
注意事項(xiàng)
你可以假設(shè)只有一組答案。
您在真實(shí)的面試中是否遇到過這個(gè)題拓提？
Yes
樣例
給出 numbers = [2, 7, 11, 15], target = 9, 返回 [1, 2].
/*
class Solution {
public:
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1+1, index2+1] (index1 < index2)
* 時(shí)間 復(fù)雜度 O(N^2)
*/
/*
vector<int> twoSum(vector<int> &nums, int target) {
// write your code here
vector<int> res;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]+nums[j]==target){
res.push_back(i+1);
res.push_back(j+1);
return res;
}
}
}
return res;
}
};
*/
class Solution {
public:
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1+1, index2+1] (index1 < index2)
* 時(shí)間復(fù)雜度 O(N)
* 空間復(fù)雜度 O(N)
*/
vector<int> twoSum(vector<int> &nums, int target) {
// write your code here
set<int> res;
//構(gòu)建一個(gè)map读恃，實(shí)現(xiàn)O(1)的元素查找
map<int, int > m;
for (int i = 0; i < nums.size(); i++) {
int key = nums[i];
int val = i;
m[key] = val;
}
for (int i = 0; i < nums.size(); i++) {
int left = target - nums[i];
auto it=m.find(left);
if (it != m.end()) {
int index = i + 1;
int left_index = m[left] + 1;
// 排除自身等于自身的情況，比如 這樣 [1,0,-1], 0
if (index != left_index) {
res.insert(index);
res.insert(left_index);
}
}
}
vector<int> ret(res.begin(), res.end());
return ret;
}
};
