写在前面

leetcode hot100 03最长连续序列解题思路

背景

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

128. 最长连续序列 - 力扣（LeetCode）

核心内容

这道题的核心是如何实现O(n)的算法，要实现O(n)的算法，只能进行简单的遍历，不能使用排序算法，为了实现快速查找则必须使用哈希结构，如果直接使用hash结构进行遍历，每个值都需要遍历一次，最差情况会是O(n^2)的算法，那么就要进行剪枝，剪去的值有两种

  1. 重复值

  2. 中间值

在hash结构中可以通过判断num-1来实现快速的确认是否为中间值，而重复值在使用Set结构时就会自动去除

踩坑记录

一开始头脑混乱，只想到了用排序实现，而没有想到可以利用hash的特点，并且没有想到可以进行剪枝

小结

在算法实现时应要仔细分析题目，确认基础数据结构以及剪枝方案