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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习