Python程式：查詢和等於目標值的不重疊子陣列的最大數量

假設我們有一個數組nums和另一個稱為target的值。現在我們必須找到不為空且不重疊的子陣列的最大數量，使得每個不同子陣列的值之和都等於target。

因此，如果輸入類似於nums = [3,2,4,5,2,1,5] target = 6，則輸出將為2，因為有兩個子陣列[2,4]和[1,5]的和等於6。

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

  • t := 一個包含單個元素0的新集合

  • temp := 0

  • ans:= 0

  • 對於nums中的每個i，執行：

    • temp := temp + i

    • prev := temp - target

    • 如果prev在t中，則

      • ans := ans + 1

      • t := 一個包含單個元素temp的新集合

    • 否則，

      • 將temp插入t

  • 返回ans

讓我們看看下面的實現以更好地理解：

示例

 線上演示

def solve(nums, target):
   t = set([0])
   temp = 0
   ans=0
   for i in nums:
      temp += i
      prev = temp-target
      if prev in t:
         ans += 1
         t = set([temp])
      else:
         t.add(temp)
   return ans
nums = [3,2,4,5,2,1,5]
target = 6
print(solve(nums, target))

輸入

"poput","vwput",9

輸出

2

更新於：2021年5月29日

146 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告