[JS] LeetCode 起步 Two Sum，面試與刷題
前陣子在投履歷，有感而發來雜談一下工程師的面試與刷題。這篇大概就是聊聊一些心得感想，然後分享一下「Two Sum」這一題。
刷題平常就要累積
很久以前剛上完 bootcamp 的課程後，曾發過一篇關於 Leetcode 初見的感想。
而在順利入職之後，我就再也沒有花時間去刷題了。畢竟這些演算法的題目其實工作上還真用不太到...... 特別是對於前端來說。除非是少數那種，閒著沒事會去解數學題的人，不然工作一忙起來，沒有特殊目標的話，可能會跟我一樣，就不會特別再花時間去刷題。
但是刷題這檔事，在我想跳槽的時候才深刻的意識到，真的平常要累積才行。不然等到要找工作時才臨時抱佛腳，就已經來不及了……
之前想跳槽時，投履歷真的吃了一個大虧。我完完全全沒有準備演算法題，然後突然被考了，當然就慘敗了。如果原本是本科生，以前就有花時間練過的話，或許突然被考一題 Easy 的題，多少還是能應付的。
但如果是跟我一樣，非本科的轉職者，原本在這方面就沒有特別花時間練過的話，除非真的很天才，不然我相信完全沒有練的情況，大腦會直接藍屏……XD
我當時就是被考了「Two Sum」，而且看到這題的瞬間，我腦袋很清楚的知道，這八成是很簡單的題目。但當下很緊張，大腦當機，而且考試用的那個線上 IDE 不熟悉，寫個 for 迴圈居然還報錯。
打開 DevTools 想檢查，結果瀏覽器跳出一堆這個 IDE 的 warring，這瞬間我直接就被掛上了「恐懼」的 debuff，之後我就呈現出一種完全無法思考的狀況。
面試官還一直安撫我說，不要緊張，慢慢來。不過我最終還是沒能把狀態找回來，理所當然那場面試也就沒下文了。
事後研究了一下該 IDE (是 CodeSanbox)，發現當時報錯的原因，只是因為預設每打一個字，就會 auto run 一次。那 for 迴圈還沒整句寫完的時候，不就會一直報錯嗎 (翻桌)。
所以我真心建議，碰到不熟的線上 IDE 時，先花時間找一下，或問一下面試官說，這有沒有 auto run 的機制，可否關掉。這還是手動 run 比較好操作，不然 console log 很髒，會搞的神經緊繃….
接著也去查了一下，發現這個 Two Sum…… 居然他喵的是 Leetcode 第一題，是第一題啊!! 連第一題都答成這樣，真的神仙都救不了我。最不愉快的就是，我事後花個不到 10 分鐘就做出來了，更加感到非常不甘心。
這一刻我才深刻的意識到，平常要多刷題，真的要多刷題。而反過來說，如果平常沒在刷題的人，突然間開始猛刷題的話，八成那個人是準備要跳槽了 (笑)。
算法題是個過濾器，不只過濾求職者，也在過濾公司
不得不說，白板題這玩意跟科舉考試類似，雖然讓人感覺好像很形式，工作上不見的用的到，考這有啥意義?
但以概率上來講，能通過考試的人，會有比較高的概率擁有更好的程式素養、team work 素質。而考不過，跑到野雞學校的人，會有比較高的概率是雷包。
這一點對於求職者篩選公司也是一樣的。不考算法題、不做技術考試，聊聊天就進去的公司，對於求職者而言也是一個高風險的事，因為你很有可能一進去就碰到雷包隊友跟隕石災難級別的老害工程師。
我後來進到了一間聊聊天就拿到 offer 的公司，三個月試用期過後，我真的馬上就想逃了。這趟短暫的旅程讓我學到了，聊聊天就能進去的公司，真的要慎重。(高階職位被挖角的情況除外)
為了脫離這囧境，如果每次考白板題我都不行，那可選擇的道路自然就會窄上一大截。所以我就暗自的下決心，我一定要拿下一間會考白板題的 offer。
終究身為工程師，白板題考不過，Easy 題都答不出來，還想談個好薪水、好公司，就真的想多了。而且對於非本科的前端，多半也不會考你那種太八股文的玩意，如果一個被認為很 common 的算法題都做不出來，就太說不過去了。
經過一番努力之後，也終於如願以償，成功拿下了人生第一場白板題考試!!
其實想說的大概也就這樣，畢竟現在工程師考試，考算法題是個大趨勢，好一點的公司都是會考的。雖然實際工作未必用的上，但花點時間投資練刷題，幫自己開拓出更寬廣的道路還是有必要的。
Leecode 第一關，Two Sum
接著來介紹一下演算法大門的第一題吧，他的象徵意義就很像英文課本的第一課、第一個單字一樣，這如果答不上來，是真的相當尷尬。
題目我就不重複貼上了，翻成中文大概就是說，會給你一個 number[]，跟一個叫做 target 的 number。陣列中必定會有一組數 numA 跟 numB 相加會等於 target。要我們找出是哪兩個數之後，用 array 格式 return 這兩數的 index，順序不拘。
// Example 1, 題目給你一數組跟一個 target
Input: nums = [2,7,11,15], target = 9// 可以找到 2 + 7 是 9
// 返回這兩數的 index 就是答案
Output: [0, 1]
個人覺得這題其實展現出算法題的特色，如果平常完全沒接觸過這種題目，排除少數天才之外，非本科生第一次看到應該是會矇掉的。甚至可能連題目在問啥都看不懂 (舉手)。
但是經過一陣子的練習之後，再回頭來看這題，就會覺得為啥當初的自己居然連這麼簡單的題目都不會 (笑)。
這題的一個關鍵思路是，能否「觀察出」這其實只是個一元一次方程式求 x。
Input: nums = [2,7,11,15], target = 9// 由於要在 Array 中去找目標, 先無腦上個迴圈
nums.forEach((num) => {
// ...
})// 上了迴圈之後就會赫然發現, 這其實只是在找 x
// 題目已知這個公式, 且 num 與 target 都知道
num + x = target// 於是就能得出
x = target - num
能否看出這點，找出 numB 會讓後續的解題變得簡單很多。而這其實也是工程師的必要技能之一「找規律的能力」。但這種數學型的觀察能力，還是要花時間去練的。
(題外話，當初被考這題時，主考官也有提示我，x 就等於 target 減去當前數。但我當下居然沒能反應過來……)
就跟前端的 DOM vs CSS vs JS 的操作熟練度一樣，沒有花時間練過的新手，可能連怎麼靈活用 JS 控制不同狀態的 DOM style 都搞不出來。
雖然解這種類數學的題，跟實際做前端操作 DOM 交互的思考方式可能差很多，但前端框架那麼多，寫法那麼多元。今天面試者 A 是用 Vue，明天的面試者 B 是熟 React，到底怎麼考才公平?? 最終，這種演算法就變成了最 common 的選項。
扯遠了。
在得出 numB 的公式之後，這題主流上有兩種思路可以解。
1. 暴力雙迴圈 (two pointer)
這種迴圈的手法，我看老外的討論，似乎會用 two pointer 這樣的詞來描述，畫成圖的話其實挺形象的，一個迴圈形同一個「指標」，兩個迴圈也就是兩個指標囉，所以叫做 two pointer。
概念上，就是先用一個迴圈去固定一個數，然後用第二個迴圈往後遍歷其他的數，這樣我們就能取得 numA 跟 numB。再配上已知的 target，就能很簡單的寫出來。
var twoSum = function(nums, target) {
// 指標 i, 標記 numA
for (let i = 0; i < nums.length; i++) {
const numA = nums[i]
const numB = target - numA // 指標 j, 標記 numB
for (let j = i + 1; j < nums.length; j++) {
if (numB === nums[j]) {
return [i, j]
}
}
}
};
這邊要注意，第二圈的 j 指標必須要排除第一圈的 numA，不然就重複搜尋了。所以 j 的起始是 i + 1，得往後推一格。
利用前面推導的公式，可以在第一圈就預知，當前的 numA 搭配的 numB 應該是多少，算出來之後，只要在第二圈去找出等於 numB 者，就是答案。(但要注意 return 的是 index)
這種多迴圈 pointer 手法，很多題都用的到。
2. 使用 memo 記小抄
這個好像術語是叫做 dictionary 來著，概念上是取「查字典」的這個查詢的動作。個人理解上，就是另外宣一個變數當作字典，把遍歷過的值記起來，然後在遍歷的過程中，去反向查找這個字典，比對目標是否存在。
Input: nums = [3,2,4], target = 6像是這組 example，可以在遍歷的當下，把遍歷過的數記起來，之後再回頭進行比對。
可以想像一下，現在遍歷到 index 0，就把 3 記下來，遍歷到 index 1 再把 2 也記下來。然後遍歷到 index 2 的時候，就回去跟方才記下來的數相加看看，就能找到跟 4 相加會等於 6 的數字 2。
思路出來之後，這種操作我們可以用 JS 的 Map 或是 object 都是可以的，因為這題的情況不需要特地去除重複者。那由於 Map 的 API 呼起來比較語意化，所以這邊用 Map 來操作。
var twoSum = function(nums, target) {
// 用字典 memo 遍歷過的數
const myMap = new Map() for (let i = 0; i < nums.length; i++) {
const numA = nums[i]
const numB = target - numA
// 查字典, 如發現 numB 已存在, 則得出答案
if (myMap.has(numB)) {
return [i, myMap.get(numB)]
}
// 把遍歷過的值往字典塞
myMap.set(numA, i)
}
};
利用這樣做一個 memo 的手法，可以直接拆掉一個迴圈，讓理論運算效能直接快上一個級數。
可以想像一下，當這個 nums 非常大，假設長度是…… 100萬好了，前者暴力迴圈的作法，就可以視同跑了 100 萬 * 100 萬圈，用那個甚麼時間複雜度來標記的話，應該就是 O(n²)。
但利用這種 memo 的小技巧，拆掉了一個迴圈，只要跑一輪 100 萬圈就夠了，時間複雜度就降成了 O(n)。這也是後續題目很常會用到的一種技巧。
這邊要特別注意的是，由於題目要求的 return 值為 index，而不是 vaule 本身。所以為了 return 操作方便，這邊 Map 在紀錄時，要把 key-value 顛倒一下。最後回傳的時候取 index 會比較方便。
3. 利用 JS API
最後再介紹一下，我個人第一次解出這題時用的思路。概念上跟雙迴圈類似，只是我嘗試利用 JS 的 API，像是甚麼 Array.findIndex() 或是 Array.indexOf() 這類既有功能，去做優化。
雖然本質上還是跟雙迴圈 + return 差不多，但這樣寫法上會比較精簡一點。
var twoSum = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
const numA = nums[i]
const numB = target - numA
// index 補正用
const offset = i + 1
// 利用 slice 取出不含 numA 右側的 Array
const idxB = nums.slice(offset).indexOf(numB)
if (idxB !== -1) {
return [i, idxB + offset]
}
}
};這個寫法乍看之下比單純雙迴圈要高級，但 indexOf 本身其實也是在遍歷，並且還多出了一個 slice 切陣列的計算量，速度上未必會比雙迴圈要快。
而且這個 offset 的 index 計算，其實看到瞬間是需要思考一下的，所以這可能不是個太直覺的寫法。
真的面試考出來，還是別寫的這麼花，乖乖用雙迴圈安全點 (笑)。
好，就醬~ 再見。
