[演算法題目] Validate Subsequence

本題資訊

難度：easy
使用語言：C++
相關概念：Arrays

題目敘述

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.

Input:

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

Output:

true

Idea

這裡注意到 subsequence 的定義，和原 array 相對應的順序要正確，但不需要是連續元素。最簡單的方式自然是逐一比對，但這樣徒增時間複雜度且沒有好好利用到這一題的性質。既然只要回傳 true 和 false，表示我們可能可以讓判斷變得更簡單。

這裡抓住「相對應的順序要正確」這一點，以及主要判斷的項目是 sequence，也就是說我們應該可以照著 sequence 的順序下去比對，對到相等的元素後 index 要前進，也就是說因為有順序性，在 array 中比對到的元素之前就不溯及過往、不再重複比對。

那實際操作上，我會希望有兩個 index 變數，一個是 arrIndex，另外一個是 seqIndex，分別記錄 array 和 sequence 目前所在位置。再來設計一個迴圈，這個迴圈中 arrIndex 會不斷往前走，而 seqIndex 則是有比對到才往前走。如果說最終 seqIndex 等於 seqIndex 的長度，那就表示每個都有比對到，也都有照著原 array 的順序排，那就是符合 subsequence 的定義了。

#include <vector>
using namespace std;

bool isValidSubsequence(vector<int> array, vector<int> sequence) {
  int arrIndex = 0;
  int seqIndex = 0;
  while (arrIndex < array.size() && seqIndex < sequence.size()){
    if (array[arrIndex] == sequence[seqIndex]){
      seqIndex++;
    }
    arrIndex++;
  }
  return sequence.size() == seqIndex;
}

時間複雜度：\(O(n)\)，\(n\) 是 array 長度
空間複雜度：\(O(1)\)