一切都是为了面试
这只是一篇单纯的心得整理,先说说为何我要刷 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 }};