LC128.最长连续序列

原题链接

思路

• 例如[4, 2, 1, 3, 100, 101, 102]

• 分成两步：

  1. 找个每个连续的部分（红圈圈起来的）具体做法：把整个数组倒进哈希表里面，如果num - 1不存在，那么num一定就是连续部分的开始。

  2. 判断每个连续部分的长度 具体做法：逐个往后读，直到哈希表中不存在该数 + 1为止

     代码

     class Solution {
     public:
     int longestConsecutive(vector<int>& nums) {
       unordered_set<int> rec;
       for (int num : nums) {
           rec.insert(num);
       }
       int max_len = 0;
       for (int num : nums) {
           int cur_len = 1;
           int cur_num = num;
           if (!rec.count(cur_num - 1)) {
               while (rec.count(cur_num + 1)) {
                   cur_len += 1;
                   cur_num += 1;
               }
           }
           max_len = max(max_len, cur_len);
       }
       return max_len;
     }
     };