第一次刷 LeetCode 就撞墙

一切都是为了面试

这只是一篇单纯的心得整理,先说说为何我要刷 LeetCode,因为听说下周的一场面试会考啊(我就是如此的肤浅),所以我就想说来简单刷个一两题也好,不然原本是想说先看完一个逻辑训练的课程后,再来刷 LeetCode。这边先推荐一下 Lidemy 的一门课程 先别急着写 leetcode,非常适合像我这种非本科系出生,逻辑又不算好的工程师,这门课程会带着你去刷很多相对 LeetCode 来说简单很多的题目,同时也会讲解题目和解答的逻辑,我觉得对提升自己的程式逻辑有不小的帮助。

什么是 Hash Table

总之,逼不得已的在今天第一次碰了 LeetCode,并选了难度 Easy 的第一题, Two Sum,题目会给予一组 array,里面会有一些 number,然后会给一个 number target,我们必须找出 array 中任两个加总为 target 的数值,并回传他们的 index。

看完题目解说后,很有自信地用两个 for 迴圈去解题,然后直接撞墙,遇上了维特大大这篇文章一样的情境 刷 LeetCode 该有的基本知识,然后我也参考了他的文章去找解答,于是看到了像是 Hash Table、时间複杂度之类的神奇事物,在网路上搜寻了文章之后,觉得资讯量一下爆炸,逼不得已,只好来做纪录。

一般来说我们储存多笔资料,是用 array 来处理,当我们要比对某一笔资料是否存在于 array 里面时,最直觉的做法就是直接 for 迴圈跑 array,直到找到一样的资料。这总做法跟我在Two Sum一开始所想的两个 for 迴圈的作法一样,如果 n 越大,两个迴圈相对就要执行越多次步骤。而 hashtable 则不一样,JS 中 hashtable 的作法是用物件的方式储存资料的 key 和 value,这样我们在对比资料时,只要呼叫 key 就能马上取得资料。

在Two Sum里,hashtable 的作法,是只跑一遍迴圈,我们以下面资料为例,我们要在 nums array 中找到加起来为 9 的两个数字,并回传他们的 index。

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
当迴圈跑到 nums[0] 的时候,我们就储存 data 2 和它的 index 0 到物件中

let number = { 2:0 }

然后继续跑回圈,每一个迴圈我们都去比对 target - nums[i] 的值是否已经储存在资料里了,如果已经存在,就表示这一个 nums[i] 和物件中已经储存的资料是我们想要的答案。

var twoSum = function(nums, target) {    const dataObj = {}    for (let i = 0; i < nums.length; i++) {        // 如果 dataOnj[nums[i]] 有数值且大于等于 0,那这笔资料和目前的 index 就是我们要回传的答案        // 以题目为例到迴圈第二次执行时, dataObj 里面应该是 { 7:0 }        // 所以 dataObj[nums[i]] 为 0`,符合条件,return 答案        if ( dataObj[nums[i]] >= 0) {            return [dataObj[nums[i]], i]        }        // 用 target 减去当前的 nums[i],将得到的数字做为 key,index 作为 value,以题目为例,第一笔存入的会是 7:0        dataObj[ target - nums[i]  ] = i    }};

参考资料

白话的 Hash Table 简介JS Hashtables vs. Arrays初学者学演算法|谈什么是演算法和时间複杂度初学者学演算法|从时间複杂度认识常见演算法

关于作者: 网站小编

码农网专注IT技术教程资源分享平台,学习资源下载网站,58码农网包含计算机技术、网站程序源码下载、编程技术论坛、互联网资源下载等产品服务,提供原创、优质、完整内容的专业码农交流分享平台。

热门文章