[LeetCode]1. Two Sum

Problem

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
5
6
Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

给定一个数组,一个数字target, 在数组中查找两个数之和等于target. 返回查找的下标.

假定每个target只有一个solution,不能重复使用元素.

Solution

Analysis

最朴素的办法: 双层循环. 时间复杂度O(N*N). 这个就不介绍了.

改进方法: O(N). 借助hash表[空间换时间]. hash表记录元素与下标对应关系. 这里我们不用事先对hash表进行初始化. 边循环数组边赋值: 如果查找元素不存在,进行赋值.

具体代码如下:

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> tabel;

vector<int> result;

for (int i=0; i< nums.size(); ++i){
// 查找数字为target-nums[i]; 如果存在说明找到答案, nums[i]也不用存到hash表,直接退出循环,返回结果
if (tabel.find(target - nums[i]) != tabel.end()){
result.push_back(tabel[target-nums[i]]);
result.push_back(i);
break;
}
// 不存在, 存入hash表
tabel[nums[i]] = i;
}

return result;
}
};
您的支持就是我更新的最大动力!谢谢!