Python程式：查詢大小至少為2且和為k的倍數的子列表

假設我們有一個非負數列表，稱為nums，以及另一個正值k。我們必須檢查是否存在任何長度至少為2的子列表，其和是k的倍數。

因此，如果輸入類似於nums = [12, 6, 3, 4] k = 5，則輸出將為True，因為子列表[12, 3]的和為15，可以被5整除。

為了解決這個問題，我們將遵循以下步驟：

• sum := 0
• m := 一個新的對映
• m[0] := -1
• 對於範圍從0到nums大小的i，執行以下操作：
  • sum := sum + nums[i]
  • sum := sum mod k
  • 如果sum存在於m中，則：
    • 如果i - m[sum] >= 2，則：
      • 返回True
  • 否則，
    • m[sum] := i
• 返回False

讓我們看看以下實現，以便更好地理解：

示例

 即時演示

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))

輸入

[12, 6, 3, 4], 5

輸出

True

Arnab Chakraborty

更新於： 2020年11月19日

102 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習