Chương trình tìm độ dài dãy con liên tiếp phần tử khác nhau dài nhất trong Python

Cho danh sách nums, tìm độ dài dãy con liên tiếp (sublist) dài nhất mà tất cả các phần tử đều khác nhau (distinct).

Ví dụ: nums = [6, 2, 4, 6, 3, 4, 5, 2] → kết quả 5 (dãy [6, 3, 4, 5, 2]).

Giải thuật (Cửa sổ trượt + Hash Map)

1. Khởi tạo head = 0 (trái cửa sổ), dct = {} lưu chỉ số cuối cùng của mỗi giá trị, max_dist = 0.
2. Duyệt i, num qua enumerate(nums):
   • Nếu và dct[num] >= head: dịch head = dct[num] + 1 (loại bỏ phần tử trùng lặp khỏi cửa sổ).
   • Cập nhật dct[num] = i.
   • Cập nhật max_dist = max(max_dist, i - head + 1).
3. Trả về max_dist.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        head = 0
        dct = {}
        max_dist = 0
        for i, num in enumerate(nums):
            if num in dct and dct[num] >= head:
                head = dct[num] + 1
            dct[num] = i
            if i - head + 1 > max_dist:
                max_dist = i - head + 1
        return max_dist

ob = Solution()
nums = [6, 2, 4, 6, 3, 4, 5, 2]
print(ob.solve(nums))  # Output: 5

Đầu vào

[6, 2, 4, 6, 3, 4, 5, 2]

Đầu ra

5