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 := 一個字典，最初為鍵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))

輸入

[5,8,6,3], 8

輸出

1

更新於： 2021年10月18日

155 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告