Задача: 128. Longest Consecutive Sequence
Сложность: medium

Найти длину самой длинной последовательности последовательных чисел в неотсортированном массиве. Время работы — O(n).

Пример:

Input: [100,4,200,1,3,2] → Output: 4

👨‍💻 Алгоритм:

1⃣Помещаем все числа в unordered_set, чтобы можно было быстро проверять наличие элемента (O(1) время доступа).

2⃣Проходим по каждому числу, и если num - 1 не существует в сете — это начало новой последовательности. Затем увеличиваем currentNum, пока currentNum + 1 есть в сете, считая длину последовательности.

3⃣После проверки каждого числа обновляем longestStreak, если текущая последовательность длиннее.

😎 Решение:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;

        for (int num : numSet) {
            if (!numSet.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.count(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
};

Ставь 👍 и забирай 📚 Базу знаний