Leetcode (28) Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
本題は1つの並べ替えられていない配列の中から最も長い連続要素の個数を探し出すことを要求して、本題の最も直感的な解法は先に並べ替えてから遍歴して、しかし《アルゴリズムの導論》を読んだことがある学生はすべて知っていて、任意の比較に基づく並べ替えアルゴリズムの時間の複雑度の下限はO(nlogn)で、時間の複雑度がO(n)の並べ替えアルゴリズムはすべて空間で時間を変える方法で、数値範囲が小さいことが要求されるが,問題に基づいて配列中の要素の数値範囲がどれだけあるか分からないため,ここでは線形ソートアルゴリズムは使用できない.
空間交換時間といえば,hash tableにより配列を補助して本題を完成させることができる.

hash tableを使用して配列内のすべての要素を保存します.

配列を巡回し、i番目の要素に対してhash tableを用いてnums[i]+k(k=1,2,3,

配列を巡りi番目の要素に対してhash tableを用いてnums[i]−k(k=1,2,3,⋅⋅⋅)が存在するか否かを順次探索し,存在しない位置まで連続要素個数cnt 2

を得る.

cnt 1+cnt 2>maxLenの場合、maxLen=cnt 1+cnt 2となる.(maxLenはi番目の要素より前の最長連続要素数)

注意すべきは、遍歴した要素ごとにhash_からtableから削除し、重複カウントを回避します.TwoSumという問題をしたことがある学生は、この2つの問題が似ていることに気づいたことがありますか?

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 1 || nums.empty())
            return nums.size();

        unordered_set<int> data;
        for(int i = 0; i != nums.size(); ++i)
            data.insert(nums[i]);

        int maxLen = 0;
        for(int i = 0; i != nums.size(); ++i)
        {
            data.erase(nums[i]);
            int cnt = 1;
            int value = nums[i] + 1;
            while ( data.find(value) != data.end() )
            {
                data.erase(value);
                cnt++;
                value++;
            }

            value = nums[i] - 1;
            while ( data.find(value) != data.end() )
            {
                data.erase(value);
                cnt++;
                value--;
            }

            if (cnt > maxLen)
                maxLen = cnt;
        }
        return maxLen;
    }
};