企业网站建设网站制作,营销网站建设评估与分析,建设工程有限公司是做什么的,好看的ppt模板#x1f345; 作者主页#xff1a;不吃西红柿
#x1f345; 简介#xff1a;CSDN博客专家#x1f3c6;、信息技术智库公号作者✌。简历模板、职场PPT模板、技术难题交流、面试套路尽管【关注】私聊我。
#x1f345; 欢迎点赞 #x1f44d; 收藏 ⭐留言 #x1f4dd;… 作者主页不吃西红柿 简介CSDN博客专家、信息技术智库公号作者✌。简历模板、职场PPT模板、技术难题交流、面试套路尽管【关注】私聊我。 欢迎点赞 收藏 ⭐留言 如有错误敬请指正 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。 示例 1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2
输入nums [3,2,4], target 6
输出[1,2]示例 3
输入nums [3,3], target 6
输出[0,1] 1.暴力求解
两层循环外层循环枚举或称作选中一个标杆内层循环从枚举值之后开始遍历计算两数的和是否等于target。如果找到了两个数那么返回这两个数的下标。
for(int i 0; i n - 1; i) {for(int j i 1; j n; j ) {if nums[i] nums[j] target...}
} 暴力求解的算法时间复杂度为指数级也就是O(n^2)
分析暴力求解我们发现存在重复搜索的情况也就是对数组中的部分数据搜索了多次。那如何只对数组中的数据搜索1次或常数级然后求解呢
我们知道寻找一个数是否存在最快的方法是通过hash表在O(1)的时间复杂度之内就可以判断是否存在某个数。 2.哈希表求解 可对数组遍历一次然后将数据存入hash表然后再遍历一次数组查找 target - currentdata 是否存在hash表中如果存在那么我们就寻找到了两个数。 题目要求我们返回数组的下标那么我们的hash表的key是数组元素的值value是下标。
这种方法在最坏的情况下对数组遍历了2次也就是算法的时间复杂度是O(2n)去掉前导系数是O(n)虽然是相比暴力求解算法的时间复杂度降低了但是还有优化的空间。
在遍历数组并将数据放入hash表的同时我们也可以find(target - currentdata)是否存在如果存在那么就找到了满足条件的两个数。
find(9-4), 存在那返回这两个数的下标如果不存在那么将 4 放入hash表。 find(9-6), 存在那返回这两个数的下标如果不存在那么将 6 放入hash表。 在遍历到元素5的时候我们find(9-5)找到了这两个数。 动画演示下这个过程 代码实现
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:hashtable dict()for i, num in enumerate(nums):# ② map中查找是否有 target - curvalue的数据if target - num in hashtable:return [hashtable[target - num], i]# ① 数组中的每个数放入map中hashtable[nums[i]] ireturn [] 热门专栏推荐 大数据集锦专栏大数据-硬核学习资料 面试真题集锦 数据仓库专栏数仓发展史、建设方法论、实战经验、面试真题 Python专栏Python相关黑科技爬虫、算法、小工具
优质好文持续更新中……✍
