leetcode 1-Two Sum问题
1 经典Two Sum问题
问题： 给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例：给定 nums = [2, 7, 11, 15], target = 9。因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]
解法1：暴力美学法
看到这一题，大家脑海里蹦出来的第一个想法应该是暴力做法，即遍历数组，并查找是否存在一个值与target-x相等的目标元素。
1class Solution {
2public:
3 vector<int> twoSum(vector<int>& nums, int target) {
4 int i,j;
5 for(i=0;i<nums.size()-1;i++)
6 {
7 for(j=1;j<nums.size();j++)
8 {
9 if(nums[i]+nums[j]==target)
10 return {i,j};
11 }
12 }
13 return {};
14 };
15};复杂度分析
- 时间复杂度：O(n^2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)的时间。因此时间复杂度为 O(n^2)。
- 空间复杂度：O(1)
解法2：两遍哈希表
为了对时间复杂度进行优化，我们需要一种时间复杂度更低的方法来查找数组是否存在目标元素。而查找索引一个非常有效的方法就是哈希表。
我们通过以空间换取时间的方式，可以将查找时间从O(n)降低到O(1)。哈希表支持以近似恒定的时间进行快速查找。之所以用近似，是因为一旦出现冲突，查找时间复杂度可能退化为O(n)，这取决于你选择的哈希函数。
我们在第一次的遍历中，将每个元素的value和它的key添加到哈希表中。然后在第二次遍历中，我们将检查每个元素对应的目标元素(target-nums[i])是否存在表中，另外我们也需要注意目标元素不能是nums[i]本身。
1class Solution {
2public:
3 vector<int> twoSum(vector<int>& nums, int target) {
4 map<int,int> a;//建立hash表存放数组元素
5 vector<int> b(2,-1);//存放结果
6 for(int i=0;i<nums.size();i++)
7 a.insert(map<int,int>::value_type(nums[i],i));
8 for(int i=0;i<nums.size();i++)
9 {
10 if(a.count(target-nums[i])>0&&(a[target-nums[i]]!=i))
11 //判断是否找到目标元素且目标元素不能是本身
12 {
13 b[0]=i;
14 b[1]=a[target-nums[i]];
15 break;
16 }
17 }
18 return b;
19 };
20};复杂度分析
- 时间复杂度：O(n),我们把包含有n个元素的列表遍历两次。由于哈希表将查找时间缩短到O(1)，所以时间复杂度为O(n)。
- 空间复杂度：O(n):我们所需要的额外空间取决于哈希表中存储的元素数量，即n。
解法三：一遍哈希表
我们仔细想想就可以明白，其实我们只需要遍历一次哈希表。我们在插入元素的同时就可以判断表中是否存在目标元素，如果已经存在，我们就可以返回我们的解。
1class Solution {
2public:
3 vector<int> twoSum(vector<int>& nums, int target) {
4 map<int,int> a;
5 vector<int> b(2,-1);
6 for(int i=0;i<nums.size();i++)
7 {
8 if(a.count(target-nums[i])>0)
9 {
10 b[0]=a[target-nums[i]];
11 b[1]=i;
12 break;
13 }
14 a[nums[i]]=i;
15 }
16 return b;
17 };
18};复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-07-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录