[算法基础题]求两数之和

今日总结

浪费生命的三座大山,迟到,防火墙,机械硬盘。

正文

算法大佬就别看来看笑话了,回吧

场景问题

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums= [5, 7, 8, 10], target= 12

因为 nums[0] + nums[1] = 5 + 7 = 12
所以返回 [0, 1]

首先这道题属于算法中的基础,难度也简单,是一道经典题目,我也没想考大家。

但是大部分人都是采用双重for来暴力解决问题,也是十分简单 但是相对于数据量大的情况下时间复杂度并非最佳。

本篇介绍的是用一遍for循环搞定, 使用 哈希表

代码实例

经过代码的实践,确保代码无误的情况下,一次搞定。

思路

在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。

须知

需要注意的是这种实现是基于语言特性原生支持HashMap
并且所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储 n 个元素。

解惑

还有许多人说 containsKey内部还是循环, 解释下错误原因,可以去看containsKey、hashMap源码,注意散列存储结构,查找是根据hashcode快速定位,通过hashcode值去快速定位。key为基本类型或String类型,都已经重写hashCode方法。所以定位很快,循环只是解决了hash冲突问题查找方案。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一、Collection集合 1.1集合体系结构【记忆】 集合类的特点​ 提供一种存储空间可变的存储模型,存储的数...
    super_hongtao阅读 305评论 0 0
  • 四、集合框架 1:String类:字符串(重点) (1)多个字符组成的一个序列,叫字符串。生活中很多数据的描述都采...
    平凡的柚子阅读 125评论 0 0
  • 四、集合框架 1:String类:字符串(重点) (1)多个字符组成的一个序列,叫字符串。生活中很多数据的描述都采...
    佘大将军阅读 771评论 0 2
  • 一、基础知识:1、JVM、JRE和JDK的区别:JVM(Java Virtual Machine):java虚拟机...
    杀小贼阅读 2,405评论 0 4
  • 今天感恩节哎,感谢一直在我身边的亲朋好友。感恩相遇!感恩不离不弃。 中午开了第一次的党会,身份的转变要...
    迷月闪星情阅读 10,607评论 0 11