小白刷力扣100（3）-最长连续序列
学习笔记：
1.什么叫时间复杂度，怎么算？
答：算法执行的「基本操作次数」的「量级」—— 简单说，就是衡量算法 “要做多少活”，只看 “工作量的大趋势”
举个生活例子：
- 你数 10 个苹果，需要数 10 次；数 100 个苹果，需要数 100 次 → 工作量和苹果数量「成正比」，时间复杂度就是
O(n)； - 你给 10 个苹果两两配对（比如比较大小），需要比 45 次；给 100 个苹果配对，需要比 4950 次 → 工作量和苹果数量的「平方成正比」，时间复杂度就是
O(n²)； - 你找字典里的 “张” 字，不用从头翻，按拼音直接找 → 工作量和字典厚度「没关系」，时间复杂度就是
O(1)。
核心特点：
- 只看「最高阶、最影响工作量的部分」，比如
n² + n + 10只保留n²，记为O(n²)； - 忽略「常数、系数、低阶项」，比如
2n简化为n（记O(n)），n + 26简化为n（记O(n)） - 常见时间复杂度排序
2.什么叫哈希集合？
哈希集合（C++ 里的unordered_set）是一种「只存值、不存键」的哈希表结构。
此题思路
1.传统的暴力枚举 一个一个问x x+1 x+2..是否存在 虽然是最直观最简单的方法，但是需要一个一个问。比如数组[1,2,3,4]，遍历到1时，会找2、3、4（长度 4）；遍历到2时，又会找3、4（长度 3）；遍历到3找4（长度 2）；遍历到4啥也找不到（长度 1）。这样最坏的情况下，时间复杂度就是O（n方）不满足条件。
2.优化思路：
当这个数是连续序列的起点的时候，我们再开始找后续的序列。否则不找。即看x-1存不存在。
这样比如数组[1,2,3,4]，对1来说，x-1=0不存在，x+1 x+2 x+3 x+4存在，记下这个连续序列的长度为4.对2、3、4来说前一个数都存在，不记录。直接只需遍历1次，时间复杂度为o（n）。
3.工具选择--哈希集合-无序效率高
4.完整思路：
把数组中的所有数放到哈希表中；
- 遍历哈希集合里的每个数
num：- 如果
num-1不在集合里（说明num是连续序列的起点）：- 从
num开始，依次找num+1、num+2... 直到找不到为止，记录当前序列长度； - 更新「最长序列长度」；
- 从
- 如果
num-1在集合里（说明num不是起点）：直接跳过，不做任何计算；
- 如果
- 最后返回最长序列长度。
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> num_set; //创建一个哈希集合unorderd_set //把数据存放到哈希集合中 for(const int&num : nums){//新版循环来遍历这个数组nums，其中用的是常量引用num const表示不修改num，&表示引用（避免拷贝） num_set.insert(num); // 插入数到集合中（自动去重，比如数组有重复的0也只存一个） } //设置初始最长序列 int longestStreak= 0; //遍历刚才存好的哈希集合 for(const int& num : num_set){ if(!num_set.count(num -1)){ //如果在这个哈希集合中num-1不存在 判断num-1是否在集合里，存在返回1，不存在返回0 int currentNum = num; //那么当且的起始数就为该数 int currentStreak = 1;//序列此刻就在这里开始计数 while(num_set.count(currentNum + 1)){ //循环条件为该数的下一个数存在 当没有下一个数的时候停止 currentNum += 1; currentStreak += 1; } longestStreak = max(longestStreak,currentStreak);//应对数组有多个连续序列 } } return longestStreak; } };