Description
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:
1
2
3
4
| Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
|
解法一 暴力法
思想：莽就对了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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 {};
}
};
|
解法二 二次循环哈希法
思想：将数组索引和值颠倒，索引变值，值变索引（map容器可实现此功能）；之后作减法找遍历一次即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> a;
vector<int> result(2,-1);
for(int i=0;i<nums.size();i++){
a.insert(map<int,int>::value_type(nums[i],i));
}
for(int i=0;i<nums.size();i++){
if(a.count(target-nums[i])>0 && a[target-nums[i]]!=i){
result[0] = i;
result[1] = a[target-nums[i]];
break;
}
}
return result;
}
};
|
解法三 一次循环哈希法
思想：与解法二相同，是解法二的优化版，更改了map函数插入数据方式，从而更新为一次循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> a;
vector<int> result(2,-1);
for(int i=0;i<nums.size();i++){
if(a.count(target-nums[i])>0){
result[1] = i;
result[0] = a[target-nums[i]];
break;
}
a[nums[i]] = i;
}
return result;
}
};
|