LeetCode1 Two Sum

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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;
}
};
分享到 评论