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 个元素。