128. 最长连续序列

class Solution {
public:
  int longestConsecutive(vector<int>& nums) {
    int Longest = 0;
    // So straightforward... Putting the whole vector into set is for both
    // deduplication and O(1) search, which is very important.
    unordered_set<int> Set(nums.begin(), nums.end());

    for (int X : Set) {
      // Do not search in the middle of consecutive sequences. This reduces a
      // lot of time consumption.
      if (Set.count(X - 1))
        continue;

      int ThisLength = 1;
      // O(1) instead of O(n) search! We can just count from X + 1 instead of X
      // since we have already counted X in the outer for-loop.
      while (Set.count(X + 1)) {
        ++X;
        ++ThisLength;
      }
      Longest = max(ThisLength, Longest);
    }
    return Longest;
  }
};

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

    for (int X : Set) {
      // Just don't cut the rope at the middle. We need it whole.
      if (Set.contains(X + 1))
        continue;

      // The outer loop is just for the X.
      int Length = 1;
      while (Set.contains(X - 1)) {
        // Lengthen the rope.
        ++Length;
        --X;
      }

      Result = max(Result, Length);
    }
    return Result;
  }
};