128. Longest Consecutive Sequence 求最长连续序列

[GH1995]

128. Longest Consecutive Sequence

Difficulty: Hard

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

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

[GH1995]

看这次提交的代码，很简洁

---

used[i] = false 说明 i 存在 true 说明 i 被用过 从 nums 里选出一个数 nums[i]，标记为 used[i] = true 表示用过 分别向左右两边展开 即length++, used[j] = true 得到某一个片段的长度 该片段长度与 longest 比较

[GH1995]

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

      for (int val:nums) {
        if (!s.count(val)) // 跳过已经擦除的元素
          continue;

        s.erase(val); // 注意这里
        int pre = val - 1, next = val + 1;
        while (s.count(pre))s.erase(pre--);
        while (s.count(next))s.erase(next++);

        res = max(res, next - pre - 1); // 注意这里，考虑 3 -1-1
      }

      return res;
    }
};