Leetcode hot100-两数之和

给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。 规则限制每种输入只会对应一个答案不能使用两次相同的元素按任意顺序返回答案即可示例演示示例1输入nums [2,7,11,15], target 9 → 输出[0,1]示例2输入nums [3,2,4], target 6 → 输出[1,2]示例3输入nums [3,3], target 6 → 输出[0,1] 思路分析为什么不选双指针根据题目两数之和很多人第一反应会想到双指针法这里我先分析题目❌题目隐含的两个致命问题数组是乱序的如果两数之和不等于目标值对指针的移动是未知的。本题需要返回原始下标如果排序后再用双指针会直接打乱索引无法得到正确结果✅当然双指针也能做用pair存储数字下标但不是最优解今天我们重点讲更高效的哈希表解法。✅ 最优解法哈希表「定一找一」思路遍历确定第一个数 → 计算目标差值 → 哈希表快速查找第二个数逻辑用哈希表unordered_map存储数组元素对应下标查找速度接近O(1)遍历数组时计算target - 当前数得到需要找的第二个数如果哈希表中存在这个差值直接返回两个数的下标如果不存在就把当前数和下标存入哈希表继续遍历总而言之就是通过求出差值检索哈希表中是否存在该差值如果存在直接返回当前循环的第一个指针和该差值在map中的值。直接上代码class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_map int,int numMap; vector int res; for(int i 0; i nums.size(); i){ // 计算需要查找的差值 int dis target - nums[i]; // 如果哈希表中存在这个差值直接返回下标 if(numMap.count(dis)){ res {i, numMap[dis]}; break; } // 不存在则将当前元素和下标存入哈希表 numMap.insert(make_pair(nums[i], i)); } return res; } };注意这里采用了unordered_map可以使得查找效率降至常数量级因为这道题使用哈希表只是为了检索表中是否存在该差值。 复杂度总结时间复杂度O(n)仅遍历一次数组哈希表查找为O(1)空间复杂度O(n)最坏情况下存储全部数组元素最后祝各位小伙伴刷题顺利早日攻克力扣高频题如果大家还有更多想看的题解或者算法讲解都可以后台私信或者留言回复我都会一一讲解。最后声明以上解法仅为本人分享并不代表是该题的最优解。