1 两数之和
强烈建议本题和167 两数之和 II - 输入有序数组对比做
暴力版
遍历每个元素,枚举数组该元素后的每个元素,判断nums[i] + nums[j] 是否等于target
- 如果是,返回
{i, j} - 如果遍历整个数组都没有找到
{i,j},返回空数组
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
时间复杂度:\(O(n^2)\)
空间复杂度:\(O(1)\)
优化版
在暴力版中,我们发现:定位元素nums[i]后,寻找元素nums[j]花费了\(O(n)\)的时间复杂度
因此可以使用哈希表进行优化,哈希表查找元素效率为\(O(1)\)
使用哈希表优化思路:
- 我们判断某个元素的值是否存在,因此该元素的值作为哈希表的key值
- 题目要求返回元素的下标,因此该元素的下标作为哈希表的value值
最简单的想法
遍历一遍数组,将每个元素加入到哈希表中
然后再遍历一遍数组,定位元素nums[i]时,通过哈希表查询是否存在target - nums[i],如果存在返回下标
需要注意的是,题目要求不能使用同一元素多次,也就是说nums[i] != hashMap[target - nums[i]]
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hashMap;
int n = nums.size();
for(int i = 0; i < n; i++){
hashMap.insert({nums[i],i});
}
for(int i = 0; i < n; i++){
int num = target - nums[i];
if(hashMap.count(num) && hashMap[num] != i){
int j = hashMap[num];
return {i, j};
}
}
return {};
}
};
以上做法使用了两次for(int i = 0; i < n; i++),我们能够在一次循环中完成整个算法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hashMap;
int n = nums.size();
for(int i = 0; i < n; i++){
int num = target - nums[i];
if(hashMap.count(num)){
int j = hashMap[num];
return {i, j};
}
// 为了不使用当前元素,判断完之后再插入
hashMap.insert({nums[i],i});
}
return {};
}
};
注意:不需要初始化往hashMap添0,因为题目限定了两个整数的和
时间复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(n)
通用框架
可惜,本节不是告诉你有多的解法,而是告诉你这种解法为什么无效
你可能会先排序,然后利用双指针找到和为目标值的两个元素,找到后返回数组下标left和right
一切都是那么完美,然而你发现没有AC,这是因为你返回的是排序后的数组下标,而题目求的是原来的数组下标
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.size() - 1;
// 不能使用两次相同元素,所以left == right没意义
while(left < right){
if(nums[left] + nums[right] == target){
return {left, right};
}else if(nums[left] + nums[right] < target){
left++;
}else if(nums[left] + nums[right] > target){
right--;
}
}
return {};
}
};
你意识到了这一点,然后用哈希表记录原来元素对应的位置
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i = 0; i < nums.size(); i++){
hashMap[nums[i]] = i;
}
sort(nums.begin(), nums.end());
int left = 0, right = nums.size() - 1;
// 不能使用两次相同元素,所以left == right没意义
while(left < right){
if(nums[left] + nums[right] == target){
return {hashMap[nums[left]], hashMap[nums[right]]};
}else if(nums[left] + nums[right] < target){
left++;
}else if(nums[left] + nums[right] > target){
right--;
}
}
return {};
}
};
在样例[3,3]上面栽跟头了,因为数组可能出现多个值,哈希表unordered_map<int,int>无法记录一个值对应的多个索引。
如果要坚持下去,我们只能给哈希表加点料了。为了解决哈希表无法记录多个索引,我们把value由int改为容器类型,选择哪个容器大有讲究,因为我们返回的时候需要按从小到大的顺序返回,然而初始化哈希表的时候容器的索引也是从小到大添加的,因此符合FIFO,为此我们选择队列
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, queue<int>> hashMap;
for (int i = 0; i < nums.size(); i++) {
hashMap[nums[i]].push(i);
}
sort(nums.begin(), nums.end());
int left = 0, right = nums.size() - 1;
// 不能使用两次相同元素,所以left == right没意义
while (left < right) {
if (nums[left] + nums[right] == target) {
int idx1 = hashMap[nums[left]].front();
hashMap[nums[left]].pop();
int idx2 = hashMap[nums[right]].front();
hashMap[nums[right]].pop();
return {idx1, idx2};
} else if (nums[left] + nums[right] < target) {
left++;
} else if (nums[left] + nums[right] > target) {
right--;
}
}
return {};
}
};
这次AC了,但是为了使用通用框架,感觉有点麻烦了,建议还是使用未排序双指针法
本次尝试告诉了我们两个tips:
- 排序后再双指针适用于求满足nSum的值,而不是下标
- 如果需要求数组下标,那么不能排序
相比之下,167 两数之和 II - 输入有序数组给出了求的是排序之后的下标,那么就可以使用通用框架。