Chương trình tìm độ dài chuỗi số liên tiếp dài nhất trong Python

Cho mảng chưa sắp xếp, tìm độ dài chuỗi các số nguyên liên tiếp dài nhất (không cần liên tiếp trong mảng).

Ví dụ: nums = [70, 7, 50, 4, 6, 5] → kết quả 4 (chuỗi [4, 5, 6, 7]).

Giải thuật (Hash Set O(n))

1. Chuyển nums thành set để truy xuất O(1).
2. Khởi tạo max_cnt = 0.
3. Duyệt từng num trong set:
   • Chỉ bắt đầu đếm nếu num - 1 không có trong set (đảm bảo num là đầu chuỗi).
   • Đếm cnt bằng cách tăng num liên tục بينما nó còn trong set.
   • Cập nhật max_cnt = max(max_cnt, cnt).
4. Trả về max_cnt.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        nums = set(nums)
        max_cnt = 0
        for num in nums:
            if num - 1 not in nums:
                cnt = 0
                while num in nums:
                    num += 1
                    cnt += 1
                max_cnt = max(max_cnt, cnt)
        return max_cnt

ob = Solution()
nums = [70, 7, 50, 4, 6, 5]
print(ob.solve(nums))  # Output: 4

Đầu vào

[70, 7, 50, 4, 6, 5]

Đầu ra

4