LC 1、两数之和
题目描述
这是LeetCode上的 1、两数之和,难度为 简单。
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出「和为目标值」的那「两个」整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
题目链接:https://leetcode.cn/problems/two-sum/
朴素解法
使用双重循环枚举下标 i 和 j,分别代表我们要找的两个数,然后判断
$$
nums[i] + nums[j] == target
$$
另外为了防止得到重复的解,我们需要在下一层循环中从 i 开始
代码:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i = 0; i < nums.size(); i++){
for(int j = i + 1; j < nums.size(); j++){
if(nums[i] + nums[j] == target){
return {i, j};
}
}
}
return {};
}
};
- 时间复杂度:双重循环,复杂度是O(n^2)
- 空间复杂度:O(1)
哈希表
首先,任何优化的思路都无外乎【减少重复】
我们可以发现,在存在着双重循环的情况下,我们其实是对数组存在着重复扫描的情况的。
举个栗子,对于 nums = [2, 3, 8 ,4]
, target = 9
的情况,我们第一个扫描的值为2,我们就要从后扫描是否有7,这时我们到了3, 所以要找6, 我们就应该利用之前找7 的时候使用的结果来帮助我们找6,而不是在进行扫描。
所以,我们使用哈希表尽心那个值的存储 key:{数值} , value:{数值下标}
代码:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int t) {
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++){
int key = t - nums[i];
if(hash.find(key) == hash.end()) hash.emplace(nums[i], i);
else return{hash[key], i};
}
return {};
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(n)
其他
可以看到,我将原题目的入参 target
替换成了 t
,但并不影响正确性,目的是为了提高编码速度。如果你也经常参与 LeetCode 周赛,就会发现这是一个常用的小技巧。 --(三叶姐)