用 Python 编写一个程序，让和可以被 P 整除

pythonserver side programmingprogramming更新于 2025/11/26 12:28:17

假设我们有一个数组 nums 和另一个值 p，我们删除最小的子数组(而不是整个数组)，使得剩余值的总和可以被 p 整除。我们必须找到需要删除的最小子数组的长度，如果没有这样的子数组则返回 -1。

因此，如果输入为 nums = [8,2,6,5,3] p = 7，则输出将为 1，因为如果我们删除 3，则总和将为 21，并且可以被 7 整除。

要解决这个问题，我们将遵循以下步骤 −

ans := infinity
s := (nums 中所有元素的总和) mod p
d := a map 包含键值对 {0: -1}
cum := 0
如果 s 与 0 相同，则
- 返回 0
for i in范围从 0 到 nums 的大小，执行
- cum := cum + nums[i]
- r := cum mod p
- 如果 (r-s)mod p 存在于 d 中，则
  - ans := ans 和 i 的最小值 - d[(r-s) mod p]
- d[r] := i
如果 ans < nums 的大小，则返回 ans，否则返回 -1

示例

让我们看看下面的实现以便更好地理解 −

def solve(nums, p):
   ans = float("inf")
   s = sum(nums) % p
   d = {0:-1}
   cum = 0
   if s == 0:
      return 0
   for i in range(len(nums)):
      cum+=nums[i]
      r = cum%p
      if (r-s)%p in d:
         ans = min(ans, i-d[(r-s)%p])
      d[r] = i
   return ans if ans<len(nums) else -1

nums = [8,2,6,5,3]
p = 7
print(solve(nums, p))