โปรแกรมหาความยาว sublist สั้นที่สุดที่ลบได้เพื่อให้ผลรวมหาร k ลงตัวใน Python

คำอธิบายปัญหา

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

ตัวอย่าง

nums = [5,8,6,3], k = 8 → Output: 1

Sum=22, ลบ [6] (len=1) → เหลือ 16 หาร 8 ลงตัว

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

1. rem = sum(nums) % k หาก 0 คืน 0
2. Prefix sum modulo k: m = presum % k
3. ต้องการหา subarray ที่ sum % k = rem → presum[j] - presum[i] ≡ rem (mod k)
4. เก็บ mp[m] = i (latest index) หา i ที่ (m - rem) % k มีใน mp

การตนการทำงาน (Python)

def solve(nums, k):
    rem = sum(nums) % k
    if rem == 0:
        return 0
    n, presum = len(nums), 0
    mp = {0: -1}
    res = n
    for i in range(n):
        presum += nums[i]
        m = presum % k
        mp[m] = i
        if (m - rem) % k in mp:
            res = min(res, i - mp[(m - rem) % k])
    return res if res != n else -1

nums = [5, 8, 6, 3]
k = 8
print(solve(nums, k))  # Output: 1

อินพุต / เอาต์พุต

Input:  [5, 8, 6, 3], 8
Output: 1