Chương trình tìm danh sách con độ dài ≥ 2 có tổng chia hết cho k trong Python

Mô tả bài toán

Cho danh sách nums (số không âm) và k > 0. Kiểm tra xem có tồn tại sublist độ dài ≥ 2 có tổng chia hết cho k hay không.

Ví dụ: nums = [12,6,3,4], k = 5 → True (sublist [12,3] tổng 15 chia hết 5).

Giải thuật (Prefix Sum Modulo + Hash Map)

1. sum = 0, m = {0: -1}.
2. Duyệt i từ 0 đến n-1:
   • sum = (sum + nums[i]) % k.
   • Nếu sum đã có trong m và i - m[sum] >= 2: trả về True.
   • Nếu sum chưa có: m[sum] = i.
3. Trả về False.

Ví dụ mã Python

class Solution:
    def solve(self, nums, k):
        sum = 0
        m = {}
        m[0] = -1
        for i in range(0, len(nums)):
            sum += nums[i]
            sum %= k
            if sum in m:
                if i - m[sum] >= 2:
                    return True
            else:
                m[sum] = i
        return False

ob = Solution()
nums = [12, 6, 3, 4]
k = 5
print(ob.solve(nums, k))

Đầu vào

[12, 6, 3, 4], 5

Đầu ra

True