โปรแกรมนับ subsequence ติดกันที่ผลรวมหาร k ลงตัวใน Python

ได้รับอาร์เรย์ nums และค่า k ต้องการหาจำนวน subsequence ติดกัน (subarray) ที่ผลรวมของสมาชิกหาร k ลงตัว

ตัวอย่าง: k = 3, nums = [1,2,3,4,1] ผลลัพธ์คือ 4 เพราะ subsequence ที่ตรงเงื่อนไขคือ [3], [1,2], [1,2,3], [2,3,4]

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

1. สร้างอาร์เรย์ x ขนาด k เติม 0 แล้วตั้ง x[0] = 1
2. กำหนด r = 0, s = 0
3. วนลูปแต่ละ elem ใน nums:
   • s = (s + elem) % k
   • r += x[s]
   • x[s] += 1
4. คืนค่า r

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

def solve(k, nums):
    x = [0] * k
    x[0] = 1
    r = s = 0
    for elem in nums:
        s = (s + elem) % k
        r += x[s]
        x[s] += 1
    return r

# ทดสอบ
k = 3
nums = [1, 2, 3, 4, 1]
print(solve(k, nums))  # ผลลัพธ์: 4

อินพุตตัวอย่าง

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

เอาต์พุตตัวอย่าง

4