โปรแกรมหาความยาวของรายการย่อยที่ไม่ซ้ำกันมากที่สุดใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องการหาความยาวของรายการย่อยที่ติดกัน (contiguous sublist) ที่มีองค์ประกอบทั้งหมดไม่ซ้ำกัน (unique)

ตัวอย่างเช่น หาก nums = [6, 2, 4, 6, 3, 4, 5, 2] ผลลัพธ์จะเป็น 5 เนื่องจากรายการย่อยที่มีองค์ประกอบไม่ซ้ำกันมากที่สุดคือ [6, 3, 4, 5, 2]

ขั้นตอนการแก้ปัญหา (Sliding Window + Hash Map)

1. กำหนด head = 0 (จุดเริ่มต้นของหน้าต่าง), dct = {} (เก็บ index ล่าสุดของแต่ละตัวเลข)
2. กำหนด max_dist = 0
3. วนลูปผ่านแต่ละ index i และ num ใน nums:
   • หาก num อยู่ใน dct และ dct[num] >= head:
     • เลื่อน head = dct[num] + 1
   • dct[num] = i
   • max_dist = max(max_dist, i - head + 1)
4. คืนค่า max_dist

ตัวอย่างโค้ด Python

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
            max_dist = max(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

อินพุต

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

เอาต์พุต

5