清风的技术小屋

不为所动, 做更专业的自己

0%

LeetCode 1 - Two Sum

问题描述:

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. Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

时间复杂度为 O(n) 解法

首先分析下问题,根据问题描述,可以得知数组是无序的。如果用暴力方法解决问题,也就是先在数组中固定一个数字,再判断数组中其余的 \(n-1\) 个数字与它的和是不是等于目标值,这样时间复杂度是 \(O(n^2)\)。这里关键地方就是在于固定一个数字时,如何快速在数组中寻找与它的和等于目标值,而不是通过遍历方法一个个找,这样时间复杂度要 \(O(n)\),想到快速查找,第一时间可以想到的是哈希表 (Hash Map),因为这个查找元素的时间复杂度为 \(O(1)\)

对于哈希表,我们可以用数组中的数字作为哈希表的key,用数字的下标作为哈希表的value。当我们从头遍历数组时,对于访问到的数字,我们首先判断哈希表中是否存在与它的和等于目标值的key,如果不存在,插入该数字到哈希表中,如果存在,算法返回两个数字对应的数组的下标。可以看出,这个算法只需要遍历一次数组,因此算法复杂度为 \(O(n)\)

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
42
43
#include <unordered_map>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> nums_map;
unordered_map<int, int>::const_iterator iter;
vector<int> indices;
for (int i=0; i<nums.size(); i++) {
if ((iter = nums_map.find(target - nums[i])) == nums_map.end()) {
nums_map.insert(make_pair(nums[i], i));
} else {
indices.push_back(iter->second);
indices.push_back(i);
break;
}
}

return indices;
}
};

int main()
{
int target = 9;
vector<int> nums;
nums.push_back(2);
nums.push_back(7);
nums.push_back(11);
nums.push_back(15);

Solution sol;
vector<int> indices = sol.twoSum(nums, target);
if (indices.size() == 0) {
cout << "Not found" << endl;
} else {
cout << "Find: [" << indices[0] << ", " << indices[1] << "]" << endl;
}
return 0;
}