Python程序：查找和能被k整除的连续子序列个数

假设我们有一个数组nums和一个值k。我们必须找到和能被k整除的连续子序列的个数。

因此，如果输入类似于k = 3 nums = [1,2,3,4,1]，则输出将为4，因为子序列为[3]，[1,2]，[1,2,3]和[2,3,4]。

为了解决这个问题，我们将遵循以下步骤：

• x := 一个大小为k的数组，并用0填充
• x[0] := 1
• r:= 0, s:= 0
• 对于nums中的每个元素，执行：
  • s :=(s + elem) mod k
  • r := r + x[s]
  • x[s] := x[s] + 1
• 返回r

示例

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

def solve(k, nums):
   x = [0]*k
   x[0] = 1
   r=s=0
   for elem in nums:
      s = (s+elem) % k
      r += x[s]
      x[s] += 1
   return r

k = 3
nums = [1,2,3,4,1]
print(solve(k, nums))

输入

3, [1,2,3,4,1]

输出

4

Arnab Chakraborty

更新于：2021年10月25日

628 次浏览

开启您的职业生涯

完成课程获得认证

开始学习