โปรแกรมนับจำนวนสับลิสต์ที่มีค่าที่ไม่ซ้ำกันพอดี k ค่าใน Python

สมมติว่าเรามีรายการตัวเลข nums และค่า k เราต้องการหาจำนวนสับลิสต์ (sublists) ที่มีค่าที่ไม่ซ้ำกัน (unique values) พอดี k ค่า

เช่น ถ้าข้อมูลนำเข้าคือ nums = [2, 2, 3, 4] k = 2 ผลลัพธ์จะเป็น 3 เนื่องจากมีสับลิสต์: [2, 2, 3], [2, 3], [3, 4]

ขั้นตอนการแก้ปัญหา (Sliding Window + At Most K)

• ฟังก์ชัน count(K) หาจำนวนสับลิสต์ที่มีค่าไม่ซ้ำ ≤ K:
  • slot := Counter(), i := res := 0
  • วน j, x ใน nums:
    • slot[x] += 1
    • while len(slot) > K: ลด slot[nums[i]], ถ้า 0 ให้ลบ, i += 1
    • res += j - i + 1
  • คืน res
• คำตอบ = count(k) - count(k-1) (หลักการ Inclusion-Exclusion)

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

from collections import Counter
class Solution:
    def solve(self, nums, k):
        def count(K):
            slot = Counter()
            i = res = 0
            for j, x in enumerate(nums):
                slot[x] += 1
                while len(slot) > K:
                    slot[nums[i]] -= 1
                    if slot[nums[i]] == 0:
                        del slot[nums[i]]
                    i += 1
                res += j - i + 1
            return res
        return count(k) - count(k - 1)

ob = Solution()
nums = [2, 2, 3, 4]
k = 2
print(ob.solve(nums, k))

ข้อมูลนำเข้า

[2, 2, 3, 4], 2

ผลลัพธ์

3