用 Python 编写程序，查找可以删除的最小子列表的长度，使总和可以被 k 整除

pythonserver side programmingprogramming更新于 2026/1/18 15:40:17

假设我们有一个包含正值的列表，称为 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 := 字典，最初存储 -1 key 0
res := n
对于范围在 0 到 n - 1 内的 i，执行
- 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))