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

更新於：2021年10月25日

628 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告