128. Longest Consecutive Sequence
Tags:
Medium
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm độ dài dãy con liên tiếp dài nhất trong một mảng số nguyên chưa được sắp xếp. Độ phức tạp O(n)
Là liên quan đến việc tìm dãy số liên tiếp có độ dài lớn nhất trong một mảng số nguyên chưa được sắp xếp. Một dãy số được gọi là liên tiếp nếu mỗi phần tử trong dãy lớn hơn phần tử trước đó đúng 1 đơn vị
Approach
Bài tập này có thể dùng cách tiếp cận sử dụng Hash Set để đạt được TC O(n)
Ý tưởng giải quyết:
Set để tra cứu O(1)Set )Time and space complexity
Solution
1function longestConsecutive(nums: number[]): number {
2 let num_set: Set<number> = new Set(nums);
3 let longest_streak = 0;
4
5 for (const num of num_set) {
6 if (!num_set.has(num - 1)) {
7 let current_num = num;
8 let current_streak = 1;
9
10 while (num_set.has(current_num + 1)) {
11 current_num++;
12 current_streak++;
13 }
14
15 longest_streak = Math.max(longest_streak, current_streak);
16 }
17 }
18 return longest_streak;
19};