在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