# #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

<br/>

<hr/>

## 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

- 通過**地址**找到該單元的記憶體位置
- 將地址形象化 → 指針
- 作個比喻，假設將電腦存儲器當成一本書，一張內容記錄了某個頁碼加上行號的便利貼，可以被當成是一個指向特定頁面的指針;根據便利貼上面的頁碼與行號，翻到那個頁面，把那個頁面的那一行文字讀出來，就相當于是對這個指針進行反參考的動作。
- 快慢指標…

- 本題雙指標為右邊上面