[Leetcode with JavaScript] 刷題筆記 — 刷題常用的三種解法 Brute Force, Hash Map, Two Pointers
我有新的部落格了，歡迎來逛逛 https://blog.jhdev.pro/
前言
這個系列是在記錄參與 ALPHA Camp A+ 人才計畫的過程中，練習刷題的想法及筆記。
這篇文章會透過上千題中 Leetcode 的第一題Two Sum 及進階題 3Sum，來說明三種基本的解題方法，分別是暴力解(Brute Force)、雜湊表 Hash Table、雙指針 Two Pointers。如果你和我一樣是剛開始刷題的話，那就繼續看下去吧～
#1 Two Sum (Easy)
Given an array of integers
numsand and integertarget, return the indices of the two numbers such that they add up totarget.You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example :
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1]題目給一個陣列 nums 及一個目標值 target，兩者都是整數，要找出兩個陣列元素相加後與目標值相等的元素之 index。
暴力解 (Brute Force)
這是我腦海中第一個想法，利用巢狀迴圈的 index i 和 j 一前一後遍歷題目給的陣列元素，再用 if 判斷兩個 index 取出的值相加後是否等於 target。
不過使用巢狀迴圈的缺點就是很費時，時間複雜度也會變成 O(n^2)，所以可以看到 Runtime 只比 17.9% 的人快。Memory Usage 則是因為沒有宣告新的變數，直接使用迴圈的 index 所以表現不錯。
雜湊表 Hash Table
之後學了 Hash Table，先透過第一次 for 迴圈將陣列 nums 中所有的元素，以 key-value pair 型式記錄到物件 map 中，這時因為 map 還是空的所以不會進到 if 條件判斷。從第二次迴圈開始 map 有資料了程式就會進入 if 條件判斷，檢查遍歷的陣列元素和物件 map 中 key-value pair 的關係。
與暴力解相比，Hash Table 的優點是有效降低時間複雜度(O(n))，可以看到 Runtime 快很多，代價是要使用比較多的記憶體空間。Hash Table 最大的好處是 input 不需要是 sorted array 也能使用。
看起來很簡單的題目，其實可以練習到不同的解法，難怪有人說越簡單的題目，其實越困難！
#15 3Sum (Medium)
Given an array
numsof n integers, are there elements a, b, c innumssuch that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
這題給了一個陣列，元素皆為整數且有正有負，要我們找出三個元素相加後為 0 的組合放進陣列回傳，且不能有重複的組合。
為避免重複，先 sort 但預設是字元大小排序 正負數混合的情況下會不如預期 例如 -1 -1 2 -2 會變成 -1 1 2 -2 但我們期待的是 -2 -1 1 2
題目要求三個數字相加為 0，假設是 num1, num2, num3，如果像是 Two Sum 那樣，先讓 num1 固定不動，那 num2 + num3 就會是 num1 的相反數，因此關鍵是要在 num1 之後的數字中，找出兩數相加等於 num1 的相反數，這個時候就相當適合使用雙指針 Two Pointers。
雙指針 Two Pointers
這個方法最重要的是 input 需為 sorted array，讓 nums 由小排到大，這樣當 num1 固定時，就可以讓 num2, num3 也就是左右指針，從 num1 之後的數字序列的「頭」和「尾」向中間「夾」。
