两数之和

两数之和

题目描述

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.

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例

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

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

解题方法

法一:暴力穷举法

遍历每个元素 x,并查找是否存在一个值与 target−x 相等的目标元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution
{
public:
//法一:暴力穷举法
vector<int> twoSum(vector<int>& nums, int target)
{
vector<int> res;
for(size_t i=0; i<nums.size(); ++i)
for(size_t j=i+1; j<nums.size(); ++j)
if( nums.at(i) == target - nums.at(j))
{
res.push_back(i);
res.push_back(j);
return res;
}
return res;
}
};

复杂度分析

  • 时间复杂度

    嵌套for循环遍历每个元素,一次for循环耗费时间O(n), 嵌套for循环时间复杂度为O($n^2$);

  • 空间复杂度

    算法除了返回数组res没有多余的内存开销,空间复杂度为O(1)。

法二:两遍哈希表

思路,创建一个哈希表将数组元素存入,然后一次for循环遍历,遍历中得到target-x的值,查找哈希表中是否含有符合条件的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//法二:两遍哈希表
vector<int> twoSum2(vector<int>& nums, int target)
{
//创建哈希表
std::map<int, int> m;
for(size_t i = 0; i<nums.size(); ++i)
m.insert(std::pair<int, int>(nums.at(i), i));

vector<int> res;
for(size_t j = 0; j<nums.size(); ++j)
{
auto t = target - nums.at(j);
auto it = m.find(t);//查找满足条件的元素
if(it!=m.end() && it->second!=j )//查找到
{
res.push_back(j);
res.push_back(it->second);
return res;
}
}
return res;
}

复杂度分析

  • 时间复杂度

    创建哈希表一个for循环耗时O(n), 遍历for循环耗时O(n), 哈希表查找耗时O(1), 总时间复杂度O(2n+1),即O(n)

  • 空间复杂度

    哈希表的内存开销取决于数组nums的容量,空间复杂度为O(n)

法三:一遍哈希表

思路,一边创建哈希表一边遍历查找符合条件的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//法三:一遍哈希表
vector<int> twoSum3(vector<int>& nums, int target)
{
vector<int> res;
std::map<int, int>m;
for(size_t i = 0; i < nums.size(); ++i)
{
auto t = target - nums.at(i);
auto it = m.find(t);
if(it!=m.end() && it->second!=i)
{
res.push_back(i);
res.push_back(it->second);
return res;
}
m.insert(std::pair<int, int>(nums.at(i), i));
}

return res;

}

复杂度分析

  • 时间复杂度

    一次for循环遍历耗时O(n), 哈希表查找耗时O(1),总时间复杂度O(n+1), 即O(n).

  • 空间复杂度

    哈希表的内存开销取决于数组nums的容量,空间复杂度为O(n)

rustic.jpg

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