腾讯云服务器搭建网站,ui设计和网站建设人员李伟宁,重庆市建设工程安全管理信息网,长沙设计公司都有哪些这里写自定义目录标题 两数之和题目解析思路解法一 #xff1a;暴力枚举 依次遍历解法二 #xff1a;使用哈希表来做优化 核心逻辑为什么之前的暴力枚举策略不太好用了#xff1f;所以#xff0c;这就是 这道题选择 固定一个数#xff0c;再与其前面的数逐一对比完后… 这里写自定义目录标题 两数之和题目解析思路解法一 暴力枚举 依次遍历解法二 使用哈希表来做优化 核心逻辑为什么之前的暴力枚举策略不太好用了所以这就是 这道题选择 固定一个数再与其前面的数逐一对比完后再将其自身放入hash表中参与匹配 的原因 代码实现 两数之和
题目解析 思路
解法一 暴力枚举 依次遍历
时间复杂度 O(n^2) 暴力枚举两层for()循环遍历O(n^2)空间复杂度 无
先固定其中一个数依次与该数之前的数相加 而 解法二 则是遍历完这个数以后将其丢入hash表中。枚举下一个数时很自然的枚举hash表中前面遍历过的数
解法二 使用哈希表来做优化 时间复杂度O(n) 由原来的 暴力枚举两层for()循环遍历O(n^2) 到 只需遍历一遍 固定一个数O(n)哈希表查找匹配的另一个数O(1) 空间复杂度O(n) 对比 暴力枚举 即可看出哈希表是用 空间换时间 核心逻辑
为什么之前的暴力枚举策略不太好用了
我们也能把所有的数都放入hash表中再由前往后遍历一遍数组再直接在hash中找匹配的数就好了为什么还要 逐一遍历再将遍历到的节点逐一放入hash表中
这是因为会出现 “恰好 遍历到的数本身也能满足匹配的要求” 的情况这违反了题目所说的需求 数组中同一个元素在答案里不能重复出现 blog.csdnimg.cn/direct/4e384c8f2ebd454f910606e12c610d2c.jpeg)
因此这种做法需要加入特判。 所以这就是 这道题选择 固定一个数再与其前面的数逐一对比完后再将其自身放入hash表中参与匹配 的原因
因此循环遍历固定一个节点遍历完后将该节点放入hash表中后继续向后遍历仅需查找前面放入hash表中的值即可就不会出现查找hash表中选中自身的情况这样的顺序避免了 出现了重复出现同一个数字 的情况 。也 不需要再处理什么边界情况 了。 代码实现
class Solution {
public:vectorint twoSum(vectorint nums, int target) { // 数 下标unordered_mapint,int hash; // nums[i],i // 遍历数组for(int i0;inums.size();i){int xtarget-nums[i];if(hash.count(x)) return {hash[x],i}; // hash[x]中 存放的就是 x的下标hash[nums[i]]i; // 遍历完后将该节点放入到hash表中}// 照顾编译器return {1,-1};}
};
