Python - Dãy con liên tiếp chứa các số liên tiếp (unique elements)

Cho danh sách nums các số duy nhất (không trùng lặp). Tìm độ dài dãy con (sublist) liên tiếp dài nhất chứa các số liên tiếp (ví dụ: 3,4,5,6,7).

Ví dụ

Input: nums = [3, 6, 7, 5, 4, 9]
Output: 5
Giải thích: Dãy con [3, 6, 7, 5, 4] chứa các số 3,4,5,6,7 (liên tiếp).

Thuật toán: Duyệt tất cả dãy con O(n²)

Với mỗi vị trí bắt đầu i, mở rộng dãy con đến j, theo dõi min và max. Nếu max - min == j - i thì các số trong dãy con là liên tiếp (vì không trùng lặp).

Mã Python

def solve(nums):
    ret = 0
    n = len(nums)
    for i in range(n):
        lhs = nums[i]  # min trong dãy con
        rhs = nums[i]  # max trong dãy con
        for j in range(i, n):
            lhs = min(lhs, nums[j])
            rhs = max(rhs, nums[j])
            if rhs - lhs == j - i:
                ret = max(ret, j - i + 1)
    return ret

# Test
nums = [3, 6, 7, 5, 4, 9]
print(solve(nums))  # Output: 5

Phân tích độ phức tạp

• Thời gian: O(n²) - 2 vòng lặp lồng nhau
• Không gian: O(1)

Lưu ý quan trọng

Điều kiện "tất cả phần tử duy nhất" là cần thiết. Nếu có trùng lặp, max - min == j - i không đủ đảm bảo các số liên tiếp (ví dụ: [1,2,2,3] có max-min=2, j-i=3 nhưng không liên tiếp).

Cải tiến O(n log n): Sắp xếp + sliding window, hoặc dùng Hash Set kiểm tra dãy liên tiếp từ mỗi số bắt đầu (LeetCode 128 - Longest Consecutive Sequence, nhưng bài đó không yêu cầu dãy con liên tiếp trong mảng gốc).