LeetCode LCR 119.最长连续序列LCR 119.最长连续序列
题面：
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
示例：
input nums = [100,4,200,1,3,2]
output 4
解析：
- 这道题目简单的思路就是，对nums中的数字进行排序，设本次遍历到的数字为num，判断num + 1是否是下一个不等于num的数字。
- 优化：
- 针对于下一个出现的数字而言，num/num + 1/others，我们可以通过降重操作来保证下一个为num + 1/others，我们一般常用的实现就是set，而set的底层就是哈希表，相对于HashMap而言，HashSet仅对键进行操作。于是乎，我们可以通过哈希表查询来完成num + 1是否存在来推进最长连续序列，这样就省去了排序所带来的时间消耗。
- 注意：若num - 1在当前set中，意味着最长连续序列，一定不是从num向后推进的。即若[num, y]满足连续序列的要求，[num - 1, y]一定也是满足要求的，故可以不判断。
-
\[nlog(n)\rightarrow n \]
复杂度
时间复杂度
\[O(n)
\]
空间复杂度
\[O(n)
\]
Code
// C++
class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> s;for (auto num : nums){s.insert(num);}int ans = 0;for (int x : s){if (s.count(x - 1)){continue;}int y = x + 1;while (s.count(y)) {y++;}ans = max(ans, y - x);}return ans;}
};
# Python
class Solution:def longestConsecutive(self, nums: List[int]) -> int:ans = 0temp = set()for num in nums:temp.add(num)for x in temp:if x - 1 in temp:continuey = x + 1while y in temp:y += 1ans = max(ans, y - x)return ans
// Rust
use std::collections::HashSet;
use std::cmp;impl Solution {pub fn longest_consecutive(nums: Vec<i32>) -> i32 {let mut temp = HashSet::new();for num in nums.iter() {temp.insert(num);}let mut ans = 0;for x in temp.iter() {if temp.contains(&(**x - 1)) {continue;}let mut y = **x + 1;while temp.contains(&y) {y += 1;}ans = cmp::max(ans, y - **x);}return ans;}
}