Leetcode

最长连续序列

本题是Leetcode Hot100中哈希表最后一道题，个人觉得难度比两数之和&&字母异位词分组高一点，但经过前两题的训练，这一题想到用哈希表并不算困难。
老规矩，先遍历。

1
2
3
for (auto &item: nums) {

}

对于数组中遍历的每一个元素item，想要知道他是否连续，很自然的，我们会想到在数组中看一看是否存在item-1和item+1。
但我们知道，数组是没有前瞻性的，我们在没有遍历到后面的元素时，根本无法预知到它的值，
所以理所当然地，如果当前被遍历的元素不存在前一个数，我们就可以将其作为起始值，将所有元素通通存储在哈希表中，不断查询起始值++，一旦查不到连续的下一个就可以结束，更新长度。
话不多说，直接上代码，疑难点笔者会给出注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 因为只要存储数值，不用存储下标，非二元组就不需要用map来存储了，改用set
// 下面这条语句的用法，是在创建哈希表的同时，从头到尾复制nums作为哈希表的元素
unordered_set<int> heap(nums.begin(), nums.end());
int len = 0;
for (auto &item: heap) {
  // heap.find(item - 1) == heap.end()的意思是当前元素没有前一个值
  if (heap.find(item - 1) == heap.end()) {
    //找个指针（并非真正的指针*p，而是逻辑上找一个）
  	int end = item;  
    // 看一下++是否存在，如果存在，找到最后一个不连续的地方
    while (heap.find(end) != heap.end()) {
      end++;
    }
    len = max(len, end - item);
  }
}
return len;

本题的思路可能并不容易想到，建议对测试用例模拟几遍，会更容易理解本题的代码。