โปรแกรมหาจำนวนองค์ประกอบที่ไม่ซ้ำในแต่ละหน้าต่างขนาด K ใน Python

สมมติว่าเรามีรายการตัวเลข nums และตัวเลข k เราต้องการหารายการของจำนวนตัวเลขที่ไม่ซ้ำในแต่ละหน้าต่างขนาด k

ตัวอย่างเช่น nums = [2, 2, 3, 3, 4], k = 2 ผลลัพธ์คือ [1, 2, 1, 2] จากหน้าต่าง [2,2], [2,3], [3,3], [3,4]

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

1. สร้าง Counter สำหรับ k องค์ประกอบแรก
2. ans = []
3. วนลูป i จาก k ถึง len(nums) - 1:
   • เพิ่ม len(c) เข้า ans
   • เพิ่ม nums[i] เข้า counter
   • ลด nums[i-k] ออกจาก counter (ลบออกถ้าเหลือ 0)
4. เพิ่ม len(c) สำหรับหน้าต่างสุดท้าย
5. คืนค่า ans

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

from collections import Counter

class Solution:
    def solve(self, nums, k):
        c = Counter()
        for i in range(k):
            c[nums[i]] += 1
        
        ans = []
        for i in range(k, len(nums)):
            ans.append(len(c))
            c[nums[i]] += 1
            c[nums[i - k]] -= 1
            if c[nums[i - k]] == 0:
                del c[nums[i - k]]
        
        ans.append(len(c))
        return ans

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

อินพุต

[2, 2, 3, 3, 4], 2

เอาต์พุต

[1, 2, 1, 2]