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;}
}