在Python中查找可以删除的最小子列表的长度，使剩余元素的总和可被k整除

假设我们有一个具有正值的列表 nums 和一个正数 k。我们必须找到最短子列表（可能为空）的长度，该子列表可以从 nums 中删除，以便剩余元素的总和可被 k 整除。但是我们不能删除整个列表。如果没有这样的子列表可以删除，则返回 -1。

因此，如果输入为 nums = [5,8,6,3] k = 8，则输出将为1，因为 [5,8,6,3] 元素的当前总和为 22。如果我们删除长度为1的子列表 [6]，则总和为16，可以被8整除。

为了解决此问题，我们将按照以下步骤进行 −

rem :=(nums 中所有元素的总和 + k）mod k
如果 rem 与 0 相同，那么
- 返回 0
n := nums 的大小
presum := 0
mp := 字典，最初对 key 0 存储 -1
res := n
对于 i 在范围 0 到 n – 1，执行以下操作
- presum := presum + nums[i]
- m :=(presum + k) mod k
- mp[m] := i
- 如果 (m – rem + k) mod k 存在于 mp 中，那么
  - res := res 与 (i – mp[(m – rem + k) mod k]) 的最小值
如果 res 不与 n 相同，则返回 res，否则返回 -1

示例

让我们看一下以下实现以更好地理解−

def solve(nums, k):
   rem = (sum(nums) + k) % 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) % k
      mp[m] = i
      if (m - rem + k) % k in mp:
         res = min(res, i - mp[(m - rem + k) % k])
   return res if res != n else -1

nums = [5,8,6,3]
k = 8
print(solve(nums, k))