#2 Validate Subsequence

tags: Array Easy

Problem

Given two non-empty arrays of integers, write a function that determines whether the second array is a subsequence of the first one.

A subsequence of an array is a set of numbers that aren't necessarily adjacent in the array but that are in the same order as they appear in the array. For instance, the numbers [1, 3, 4] form a subsequence of the array [1, 2, 3, 4], and so do the number [2, 4]. Note that a single number in an array and the array itself are both valid subsequences of the array.

Sample Input

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

Sample Output

true

---

Solutions

My own

function isValidSubsequence(array, sequence) {
  let idx = 0;

  for(let i = 0; i < array.length; i++){
    if(array[i]===sequence[idx]){
      idx++
    }
  }
  return idx === sequence.length
}

Official answers
option 1

time O(n) space O(1)
function isValidSubsequence(array, sequence) {
  let seqIdx = 0;

  for(const value of array){
    if(seqIdx === sequence.length) break;
    if(sequence[seqIdx] === value) seqIdx++;
  }
  return seqIdx === sequence.length;
}

option 2

time O(n) space O(1)
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;
}

key point

• use for … of
  • 可直接取 array 資料，但不可用在 object 資料，需搭配 Object.keys()
  • 可用 break 中斷，map、forEach 不可中斷
  • for … in 裡，break、continue 沒作用

補充：指針、指標 Pointer

• 通過地址找到該單元的記憶體位置

• 將地址形象化 → 指針

• 作個比喻，假設將電腦存儲器當成一本書，一張內容記錄了某個頁碼加上行號的便利貼，可以被當成是一個指向特定頁面的指針;根據便利貼上面的頁碼與行號，翻到那個頁面，把那個頁面的那一行文字讀出來，就相當于是對這個指針進行反參考的動作。

• 快慢指標…
  

• 本題雙指標為右邊上面