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

本贴最后更新于 1793 天前,其中的信息可能已经东海扬尘

本文由黑壳博客原创

本文来源[算法基础题]求两数之和

今日总结

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

正文

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

场景问题

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

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

示例:

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

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

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

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

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

代码实例

twosum.png

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

思路

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

须知

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

解惑

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

About

欢迎在评论写下你的程序员趣事~~

欢迎加入我们的小组织 ,大家都叫壳叔,期待你的到来。

我们也会定期在群内聊天记录中抽取有趣的事情或者小问题。

欢迎关注公众号

![黑壳博客微信公众号]
QRCode.jpg

还有同学们的 Group 是一个能让你暖心的地方

Group 企鹅群:200408242

  • 黑壳网
    68 引用 • 44 回帖 • 2 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3186 引用 • 8212 回帖
  • 算法
    428 引用 • 254 回帖 • 24 关注
  • 壳叔
    48 引用 • 31 回帖
1 操作
ykz200 在 2019-12-09 08:28:49 更新了该帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • 图片都挂了 😂

  • someone
    作者

    我这里移动和电信网络显示正常的,有可能是地区网络原因

  • SignV

    containsKey 是用 hash 那 List 的那个 contains 方法呢 那个我记得应该是真的循环

  • someone
    作者

    道歉才看到,首先 containsKey 方法底层是调用 getNode 是 Map.get 方法的具体实现,其次 方法内注释提到 always check first node 满足不会遍历对比,反之才会需要会进行遍历对比。 如有该有误解,我一定改正。