problem

輸入為兩個陣列，皆不為空陣列且元素皆為整數，回傳第二個陣列是否為第一個陣列的子序列 (subsequence)。

sample input:
array = [5, 1, 22, 25, 6, -1, 8, 10]
sequence = [1, 6, -1, 10]

sample output:
true

子序列 (子數列) 的定義是一個序列刪掉 0 個或多個元素，且不改變剩餘元素順序的情況下，所得到的序列。換句話說，子序列的所有數字都出現在原序列中，並且維持在原序列中的順序。

例如 [1, 3, 4] 和 [2, 4] 都是 [1, 2, 3, 4] 的子序列，而 [1] 也是 [1] 的子序列。

解這題的邏輯很直覺，就是遍歷兩個輸入陣列，按照第二個陣列的順序，逐一檢查數字是否在第一個主要陣列中。
例如兩個陣列，
[5, 1, 22, 25, 6, -1, 8, 10]
[1, 6, -1, 10]

1. 以迴圈看過第一個陣列，檢查 1 有沒有在其中。
2. 有出現，才檢查下一個數字 6，否則迴圈繼續往下。
3. 迴圈跑完或所有的數字都找到後，則回傳結果。

n 為主要陣列長度
time: O(n) 當然也會有一些不需要跑完迴圈、提早結束的情況，但基本上需要迴圈過主要陣列。
space: O(1)

基於以上想法，程式碼可以分為兩種，一種使用 while 迴圈，一種使用 for 迴圈。

第一種 while 迴圈的寫法，

1. 初始化兩個指標，分別指向兩個陣列第一個位置。
2. 將兩個陣列的數字相比，如果相同，更新第二個陣列的指標。然後無論相比結果如何都更新第一個陣列指標。
3. 在陣列範圍內，重複步驟 2，最後回傳結果。
   判斷結果的方式是，如果第二個陣列長度為 n，則每個數字都有出現在第一個陣列的話指標會被更新 n 次，所以最後用指標是否等於陣列長度來判斷是否為子序列。

function isValidSubsequence(array, sequence) {
  let arrIdx = 0;
  let seqIdx = 0;
  while (arrIdx < array.length && seqIdx < sequence.length) {
    if (array[arrIdx] === sequence[seqIdx]) seqIdx++;
    arrIdx++;
  }
  return seqIdx === sequence.length;
}

第二種是 for 迴圈的寫法，邏輯一樣，只需要第二個陣列的指標，且保留了找到數字才更新指標的部份。另外，for 迴圈中並沒有檢查是否超出陣列範圍這一段 seqIdx < sequence.length，所以要將判斷加在迴圈中。

function isValidSubsequence(array, sequence) {
  let seqIdx = 0;
  for (const value of array) {
    if (seqIdx === sequence.length) break;   // 此處也可以直接回傳 true
    if (sequence[seqIdx] === value) seqIdx++;
  }
  return seqIdx === sequence.length;
}

這個題目和解雖然現在看好像簡單到不能再更簡單，但當初看時，其實有點算是學習 '將文字邏輯轉成程式碼' 的第一步。因為在還沒有用指標、物件做輔助的概念時，如果單純看到 '檢查兩個陣列' 這類描述，肯定是想著怎麼對陣列本身動手腳吧，就會寫出雜亂、容易出錯的程式碼。所以這一題算是稍微練習了如何用程式碼適合的方式保持語意化邏輯。