LeetCode 筆記 - 128. Longest Consecutive Sequence

題目在此 128. Longest Consecutive Sequence

給一個數列,請計算出最長連續子序列的長度
請實作出 time complexity O(n) 的演算法

解題思維

我覺得這題非常有趣,當初也是撞牆了不少次

這題關鍵是每個數字判斷一次就好,所以當我們看到一個數字,就可以左邊右邊延伸看看
看看可以延伸到多長

看過的數字就可以丟掉了

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:

if (size := len(nums)) <= 1:
return size

nums = set(nums)

result = 0
while nums:
n = nums.pop()

left_count = 1
while n - left_count in nums:
nums.remove(n - left_count)
left_count += 1

right_count = 1
while n + right_count in nums:
nums.remove(n + right_count)
right_count += 1

result = max(result, left_count + right_count - 1)

return result

也許你也會想看看