โปรแกรมหาจำนวนสับลิสต์ที่ผลรวมเท่ากับ k ในรายการไบนารีใน Python

สมมติว่าเรามีรายการไบนารีที่มีแค่ 0 และ 1 เรายังมีอินพุตอีกตัวคือ k เราต้องหาจำนวนสับลิสต์ (sublist) ที่ผลรวมเท่ากับ k

เช่น ถ้าอินพุตคือ nums = [1, 0, 0, 1, 1, 1, 0, 1], k = 3 ผลลัพธ์จะเป็น 8 เพราะสับลิสต์คือ [1,0,0,1,1], [0,0,1,1,1], [0,0,1,1,1,0], [0,1,1,1], [0,1,1,1,0], [1,1,1], [1,1,1,0], [1,1,0,1]

ขั้นตอนการแก้ปัญหา

1. sums := แมปเริ่มต้นมีค่า 1 สำหรับกุญแจ 0
2. r_sum := 0, ans := 0
3. สำหรับแต่ละ x ใน nums:
   • r_sum := r_sum + x
   • ans := ans + (sums[r_sum - k] ถ้ามี มิฉะนั้น 0)
   • sums[r_sum] := 1 + (sums[r_sum] ถ้ามี มิฉะนั้น 0)
4. คืนค่า ans

ตัวอย่างการใช้งาน

def solve(nums, k):
    sums = {0: 1}
    r_sum = 0
    ans = 0
    for x in nums:
        r_sum += x
        ans += sums.get(r_sum - k, 0)
        sums[r_sum] = sums.get(r_sum, 0) + 1
    return ans

nums = [1, 0, 0, 1, 1, 1, 0, 1]
k = 3
print(solve(nums, k))

อินพุต

[1, 0, 0, 1, 1, 1, 0, 1], 3

เอาต์พุต

8