C++ 中最長連續子序列

---

給定一個整數陣列，確定最長子序列的長度，其中元素是連續整數，無論它們在子序列中的順序如何。

輸入

arr = {100, 4, 200, 1, 3, 2}

輸出

Length of the longest consecutive sequence is: 4

最長連續子序列的不同方法

以下是獲取最長連續子序列的方法

• 透過排序陣列
• 透過使用集合

方法 1：透過排序陣列

以下是使用陣列在 C++ 中獲取最長連續子序列的步驟

• 使用內建排序函式對給定陣列進行排序。
• 維護兩個變數 ans 和 cnt。將 cnt 初始化為 1。
• 執行一個迴圈，從 i = 1 到陣列的大小。每當 arr[i] = arr[i-1] + 1 時，將 cnt 加 1；否則，將 cnt 重置為 1。如果 arr[i] 等於前一個元素，則不要修改 cnt 變數。
• 使用當前 cnt 和 ans 的最大值更新 ans 變數。

示例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestConsecutiveSequence(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    if (arr.empty()) return 0;

    int ans = 1;
    int cnt = 1;
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] == arr[i - 1] + 1) {
            cnt++;
        } else if (arr[i] != arr[i - 1]) {
            cnt = 1;
        }
        ans = max(ans, cnt);
    }

    return ans;
}

int main() {
    vector<int> arr = {100, 4, 200, 1, 3, 2};
    cout << "Length of the longest consecutive sequence is: " << longestConsecutiveSequence(arr) << endl;
    return 0;
}

輸出

Length of the longest consecutive sequence is: 4

時間複雜度：O(N log N)，因為排序陣列需要 O(N log N) 時間。
空間複雜度：O(1)，假設排序演算法是在原地完成的。

方法 2：透過使用集合

以下是使用集合在 C++ 中獲取最長連續子序列的步驟

• 將所有元素插入到一個集合中。
• 遍歷陣列，從 i = 0 到 i = n。
• 在每次迭代中，檢查 arr[i - 1] 是否存在於集合中。如果存在，則繼續進行下一次迭代；否則，轉到步驟 4。
• 初始化一個變數 cnt 並將其設定為 1。當集合包含下一個數字時，將 cnt 加 1。
• 使用當前 cnt 和 ans 的最大值更新 ans 變數。
  

示例

#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

using namespace std;

int longestConsecutiveSequence(vector<int>& arr) {
    unordered_set<int> elements(arr.begin(), arr.end());
    int ans = 0; 
    for (int i = 0; i < arr.size(); i++) {
        if (elements.find(arr[i] - 1) == elements.end()) {
            int cnt = 1;
            int current = arr[i];
            while (elements.find(current + 1) != elements.end()) {
                cnt++;
                current++;
            }
            ans = max(ans, cnt);
        }
    }

    return ans;
}

int main() {
    vector<int> arr = {100, 4, 200, 1, 3, 2};
    cout << "Length of the longest consecutive sequence is: " << longestConsecutiveSequence(arr) << endl;
    return 0;
}

輸出

Length of the longest consecutive sequence is: 4

時間複雜度：O(N)，因為將元素插入集合需要 O(1) 時間，並且此操作執行了 N 次。

空間複雜度：O(N)，因為使用集合儲存 N 個元素。