给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法一 :暴力运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
if (nums.size() < 2)
{
return result;
}

for (int i=0; i<nums.size(); i++)
{
bool find = false;
for (int j = i+1; j < nums.size(); ++j)
{
if (nums[i]+nums[j] == target)
{
result.push_back(i);
result.push_back(j);
find = true;
break;
}
}
if (find)
{
break;
}
}

return result;
}
};

解法二 :转map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
if (nums.size() < 2)
{
return result;
}

map<int, int> mapNums;
for (int i = 0; i < nums.size(); ++i)
{
int num = nums[i];
mapNums[num] = i;
}

// map<int,int>::iterator it = mapNums.begin();
// while(it != mapNums.end())
// {
// cout << it->first << " " << it->second << endl;
// it ++;
// }

for (int i = 0; i < nums.size(); ++i)
{
int otherValue = target - nums[i];
map<int, int>:: iterator it = mapNums.find(otherValue);
if (it != mapNums.end() && it->second != i)
{
result.push_back(i);
result.push_back(mapNums[otherValue]);
break;
}
}

return result;
}
};

解法三:转map减少循环次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
if (nums.size() < 2)
{
return result;
}

map<int, int> mapNums;
for (int i = 0; i < nums.size(); ++i)
{
int otherValue = target - nums[i];
map<int, int>:: iterator it = mapNums.find(otherValue);
if (it != mapNums.end() && it->second != i)
{
result.push_back(mapNums[otherValue]);
result.push_back(i);
break;
}

int num = nums[i];
mapNums[num] = i;


}

return result;
}
};

解法四:继续优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {

vector<int> result;
map<int, int>:: iterator it;
map<int, int> mapNums;
for (int i = 0; i < nums.size(); ++i)
{
mapNums.insert(make_pair(nums[i], i));
it = mapNums.find(target - nums[i]);
if (it != mapNums.end() && it->second != i)
{
result.push_back(i);
result.push_back(it->second);
return result;
}
}
return result;
}
};