第一次刷 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
    }
};

参考资料

1. 白话的 Hash Table 简介
2. JS Hashtables vs. Arrays
3. 初学者学演算法｜谈什麽是演算法和时间复杂度
4. 初学者学演算法｜从时间复杂度认识常见演算法