刷題筆記 — Array (4)
本系列文章是分享我在 Leetcode 及 Algoexpert 的刷題經驗，這篇文章是 Array 篇的第四篇文章。
本系列文章都假定讀者具有基礎的 complexity analysis 概念以及基礎的 Java 能力。為了不讓閱讀時間過長，每篇都只會講解 3 道題目。
每道題目我都會分為 Description(問題描述)、Examples(測資範例)、Solution(解法)、Implementation(實作) 等區塊來進行講解。但如果礙於篇幅問題或是該解法比較不理想（太複雜、效率太差）我可能就只會進行概念上的講解，並不會實際寫出 code implementation。
另外，為了讓讀者能更佳地了解，當我提及程式碼的變數時，我會將該字反白（如 variable ）。
👉 上一篇：刷題筆記 — Array (3)
如欲觀看所有系列文章，可點下面連結前往。
https://medium.com/citychaser/coding-questions/home
好了，廢話不多說，讓我們開始吧！
1. Two-Sum
Description
給定一個 non-empty array of integers array 以及一個 integer target ，從 array 當中找出一組兩個數字，使得這兩個數字相加會等於 target 。
如果有該組數字的話，將兩個 integer 以一個 array 回傳；如果找不到，則回傳一個空的 array。
array 中至多只會有一組數字相加等於 target ，同一個數字不能使用兩次，所謂的同一個數字並非指數值相同，而是在 array 中同個位置的數字只能使用一次。
Examples
Input:
array = [3, 5, -4, 8, 11, 1, -1, 6]
value = 10Output: [11, -1] (順序相反也可)
------------------------------------
Input:
array = [4, 6, 1, -3]
value = 3Output: []
Solution 1 — Brute Force
第一個解法就是用暴力解，我們要找兩個數字相加會等於 target，那就找出所有組合。第一層 for-loop 迭代每個整數，第二層再迭代該整數往右的所有整數，這樣就會得到所有組合。
兩兩一組，總共會有 N(N-1)/2 這麼多組。接著，一組一組去檢查兩數相加是否等於 target，這樣一來，總 time complexity 會是 O(N²)。
Solution 2 — Binary Search
如果今天把 array 進行 sorting ，那麼在每個整數要去找另一個整數時，就不需要將剩下的所有整數都找一遍，我們可以用 binary search 去找，這樣就只需要 O(logN)。
array = […, 3, 10, -1, 6, 17, ….]
target = 10array = […, 3, 5, 6, 10, 12, …]
可以看到，假設現在第一層輪到 3 這個整數，如果 array 沒有進行過 sorting，那就必須要往後找每一個數字 (10 -> -1 -> 6 -> 17…)，因為我們不曉得哪一個才會剛好等於 target - 3。但是如果 array 是 sorted，那就不用一個一個找，只要從 array 的中間開始找，太大就往左邊找、太小就往右邊，每次都可以砍掉一半，最多只需要找 logN+1 次。
迭代每個整數會需要 N 個 operation，而每個整數又會花 logN 個 operation 去進行 binary search，所以找到相加等於 target 的兩個數字的 time complexity 為 O(NlogN)。
但是別忘了，我們還要再加上 sorting 本身消耗的時間，大部分程式語言內建的 sorting method 基於 merge sort, quick sort, heap sort 這些方法，它們的 time complexity 大多都接近 O(NlogN)。
所以 total time complexity 會是 O(2NlogN)，但是係數會被去掉，因此是 O(NlogN)。
Solution 3 — Two Pointer
跟 solution 2 一樣，我們要先將 array 進行 sorting，但是這次我們不使用 binary search，而是在 array 的頭跟尾放上兩個 pointer ( head , tail)。
查看 head , tail 指到的整數相加是否等於 target，如果等於就回傳這兩個整數。如果小於 target，那就把 head 往左移，因為 array 是 sorted，所以越往右會是越大的整數；反之，如果大於 target，則把 tail 往左移，如此重複直到兩者重疊為止。
相比於 binary search 的 O(NlogN)，two pointer 只需 O(N) 即可完成，雖然說因為 sorting 就已經花掉 O(NlogN)，所以從總體來看兩者的 time complexity 是一樣的，但是當 input data 沒有很大的時候，兩者就會有差別。
Solution 4 — Hash / Set
這個方法是以「空間」換取「時間」，我們把出現在 array 裡的整數丟進去 Set 中。在迭代的過程中，我們只需要去找 target 跟現在迭代到的整數的「差」是不是在已經存在於 Set 中，如果存在的話，則回傳這兩個數字；如果不存在，則把現在迭代到的整數加進去 Set。
2. Validate Subsequence
Description
給定兩個 non-empty array of integers array, sequence，撰寫一個 function 判斷 sequence 是不是 array 的 subsequence。
所謂 subsequence 是指 subsequence array 中整數排列的順序與 main array 一致，但是並不需要完全相鄰。
舉例來說，array = [1, 2, 3, 4]，[1, 3, 4] 是一個 valid subsequence，[2, 4]、[1]、[1, 2, 3, 4] 也都是，但是 [1, 3, 2] 不是。
Examples
Input:
array = [5, 1, 22, 25, 6, -1, 8, 10]
sequence = [1, 6, -1, 10]Output: true
Solution — Two Pointer
是的，又要來用我們用到爛的 two pointer 了 😂
使用兩個 pointer 分別指向 array 與 sequence 的開頭。如果當下兩個指到的整數相同，則將兩者都往右移；如果不一樣，那就只移動 array 的 pointer，直到 array 或是 sequence 所有的元素都迭代完為止。
最後只要看 sequence 的 pointer 是不是指到最後一個元素，就可以知道 sequence 的每個整數是不是按照此順序都出現在了 array 裡。
因為只有將 array 和 sequence 迭代一次，所以 time complexity 為 O(N) 。
3. Spiral Traverse
Description
給定一個 nxm 的二維陣列，回傳一個一維陣列，陣列裡的元素必須照螺旋的順序排列。
所謂螺旋是指從陣列的左上角開始往右移動，到最右邊後開始往下，到最下面再往左，到最左邊後往上。
Examples
Input: [
[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7]
]Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
Solution 1 — Change Directions
使用一個變數紀錄方向，最一開始是往右，接著碰到邊緣後變成往下，再碰到邊緣就往左，再碰到邊緣往上，以此類推。但是這個做法稍嫌複雜，我們就不介紹這個方法。
Solution 2 — Divide and Conquer
另一個作法是，我們把這個矩陣想像成一個洋蔥，洋蔥的皮都是一層一層的，我們每次先專注在最外面那層，從最左上依照順時鐘順序走，走完了之後，我們就把這層給剝掉，然後從下一層的起點開始繼續。
用上面 example 的矩陣來舉例，第一層就會是 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 。
原本是 4x3 的矩陣，現在我們迭代完了最外面的這一層，所以只剩下裡面 2x1 的矩陣了，然後我們再對這個 2x1 的矩陣做一樣的操作，2x1 的走完了以後，發現只剩 0x0，也就走完了。
我們必須要知道現在剝掉的這一層的界線在哪，所以我們必須要有變數來紀錄邊界，總共會需要四個邊界來紀錄（上、下、左、右）。
以下就來看要怎麼實作。
因為要 traverse 將 array 裡的所有元素，所以不管是使用哪個 solution，time complexity 都是 O(NM) 。
今天的刷題分享就到這邊了，如果有什麼指教或是建議，歡迎在這篇文章底下留言；如果覺得這篇文章不錯，也歡迎給我點掌聲！
