LeetCode 0001 - Two Sum
# Hints
- 水题
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Easy |
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].
# 题意
给定一个长为 的数组,给定一个整数 ,求出一个二元组 ,满足 。如果有多组解,求出任意一组解即可。
# 题解
暴力枚举的做法很显然,时间复杂度为 。也容易想到枚举其中一个数然后二分查找另一个数(当然,需要先排序),时间复杂度为 。这两种方法都非常简单,此处不予赘述。
我们维护一个哈希表或者unordered_map,记录数组中每个数值对应的下标,初始为空。我们依次遍历数组中的每个元素,查找表中此时是否有键为 的记录,如果找到则返回答案,否则将 插入表中。而且问题只需要求出任意一组解,我们甚至不需要考虑哈希冲突的问题。
因为unordered_map是 操作的,所以总的时间复杂度为 。
# AC代码
class Solution {
public:
vector<int> twoSum(vector<int> & nums, int target) {
// 求解
unordered_map<int, int> ump;
for (int i = 0; i < nums.size(); i ++) {
// 查找
int val = target - nums[i];
if (ump.find(val) != ump.end()) {
return vector<int>({ump[val], i});
}
// 插入
ump[nums[i]] = i;
}
// 返回
return vector<int>({-1, -1});
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01