LeetCode1 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.

样例

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

给定一个数组和一个目标数字,若数组中某两个数字之和等于目标数字,输出它们两个的下标。

一个直观的想法是通过暴力枚举。复杂度$\mathcal{O}(n^2)$

另一个想法是把数组中的元素放入哈希表中,当枚举到array[i]时,只要查询 target - array[i] 是否存在于哈希表中即可。复杂度$\mathcal{O}(nlogn)$

代码

暴力版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int size = nums.size(), flag = 0;
vector<int> index;
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
if (i != j && nums[i] + nums[j] == target) {
index.push_back(i);
index.push_back(j);
flag = 1;
break;
}
}
if (flag) break;
}
return index;
}
};

哈希表版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> hashTable;
int size = nums.size();
for(int i = 0; i < size; ++i) {
hashTable[nums[i]] = i;
}
vector<int> index;
for (int i = 0; i < size; ++i) {
int num = target - nums[i];
if (hashTable.find(num) != hashTable.end()) {
if (i != hashTable[num]) {
index.push_back(i);
index.push_back(hashTable[num]);
break;
}
}
}
return index;
}
};