【LeetCode 128】 最长连续子序列
判断前一位数在不在字典中是这道题的关键之处，这样就可以避免重复查找，从而达到O(n) 的时间复杂度。如果没有这个判断，那么时间复杂度最坏也得是O(N^2)级别的。
1. 题目
2. 分析
- 合理利用数据结构。本题中使用了set来保存数组的元素，这是为了加快数据的查找。
- 聪明地利用规则，从而进一步减少时间复杂度。
3. 代码
class Solution:def longestConsecutive(self, nums: List[int]) -> int:if len(nums) == 0:return 0 nums_set = set(nums) # 使用set存储便于查找max_res = 1for i in nums:# 如果i-1 不在set中，那么就必须亲自下场计算值# 正是这个if 保证了 O(n) 时间复杂度if i-1 not in nums_set:cnt = 1start = i+1while(start in nums_set):cnt+=1start += 1max_res = max(max_res, cnt)return max_res