leetcode001

两和

问题描述

原文
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:
Given nums = [2, 7, 11, 15], target = 9,


1
2
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

翻译

给定一个整数数组,返回两个数字的索引,使它们相加到一个特定的目标。

您可以假设每个输入都只有一个解决方案,而您可能不会使用相同的元素两次。

例:


1
2
3
4
给定nums = [271115],target = 9

因为nums [ 0 ] + nums [ 1 ] = 2 + 7 = 9
返回[ 01 ]。

  • 法一

    class Solution {
    
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
public:

vector<int> twoSum(vector<int>& nums, int target) {

vector<int>result;

for (int i=0; i<nums.size(); i++)

{

for (int j=i+1; j<nums.size(); j++)

{

if (nums[i]+nums[j] == target)

{

result.push_back(i);

result.push_back(j);

break;

}

}

}

return result;

}

};
  • 法二
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
39
40
41
class Solution {

public:
vector<int> twoSum(vector<int>& nums, int target) {

map<int, int> mapping;

vector<int> result;

for (int i = 0; i < nums.size(); i++)

{

mapping[nums[i]] = i;

}

for (int i = 0; i < nums.size(); i++)

{

int searched = target - nums[i];

if ( mapping.at(searched) != i)

{

result.push_back(i);

result.push_back(mapping[searched]);

break;

}

}

return result;

}
};

总结

法一的解决方法思路很简单直白,直接按照排列组合的方式去组合每一种可能,知道找到nums[i]+nums[j] = target。算法复杂度为n^2。

法二相对法一进行了一点改进,使用map容器先存好nums的键值对,直接只用一层循环遍历,target-nums[i] =
search;然后直接在存好的mapping里面寻找。算法复杂度为2n

-------------本文结束感谢您的阅读-------------