128. Longest Consecutive Sequence

public class Solution {
    private bool ArrayContains(int[] arr, int num) {
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] == num) {
                return true;
            }
        }
        return false;
    }
    public int LongestConsecutive(int[] nums) {
        int longestStreak = 0;
        for (int i = 0; i < nums.Length; i++) {
            int currentNum = nums[i];
            int currentStreak = 1;
            while (ArrayContains(nums, currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }
            longestStreak = Math.Max(longestStreak, currentStreak);
        }
        return longestStreak;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private bool ArrayContains(vector<int>& arr, int num) {
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] == num) {
                return true;
            }
        }
        return false;
    }
    public int LongestConsecutive(vector<int>& nums) {
        int longestStreak = 0;
        for (int i = 0; i < nums.size(); i++) {
            int currentNum = nums[i];
            int currentStreak = 1;
            while (ArrayContains(nums, currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }
            longestStreak = max(longestStreak, currentStreak);
        }
        return longestStreak;
    }
}

class Solution {
    private boolean arrayContains(int[] arr, int num) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) {
                return true;
            }
        }

        return false;
    }

    public int longestConsecutive(int[] nums) {
        int longestStreak = 0;

        for (int num : nums) {
            int currentNum = num;
            int currentStreak = 1;

            while (arrayContains(nums, currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }

        return longestStreak;
    }
}

var longestConsecutive = function (nums) {
    let longestStreak = 0;
    for (let num of nums) {
        let currentNum = num;
        let currentStreak = 1;
        while (nums.includes(currentNum + 1)) {
            currentNum += 1;
            currentStreak += 1;
        }
        longestStreak = Math.max(longestStreak, currentStreak);
    }
    return longestStreak;
};

func arrayContains(arr []int, num int) bool {
    for i := 0; i < len(arr); i++ {
        if arr[i] == num {
            return true
        }
    }
    return false
}

func longestConsecutive(nums []int) int {
    longestStreak := 0
    for _, num := range nums {
        currentNum := num
        currentStreak := 1
        for arrayContains(nums, currentNum+1) {
            currentNum += 1
            currentStreak += 1
        }
        if currentStreak > longestStreak {
            longestStreak = currentStreak
        }
    }
    return longestStreak
}

Explanation

Algorithm

Пример:

Input: nums = [100,4,200,1,3,2]

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

👨‍💻

Алгоритм:

1️⃣

Проверка базового случая:

Перед началом работы проверяем базовый случай с пустым массивом.

Самая длинная последовательность в пустом массиве, очевидно, равна 0, поэтому мы можем просто вернуть это значение.

2️⃣

Обработка чисел в массиве:

Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).

Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.

Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3️⃣

Завершение обработки и возврат результата:

В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).

Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎