Python程式：查詢子列表數量，其和等於給定目標值

假設我們有一個名為 nums 的數字列表和另一個值 target，我們需要找到和等於 target 的子列表的數量。

因此，如果輸入類似於 nums = [3, 0, 3] target = 3，則輸出將為 4，因為我們有以下和為 3 的子列表：[3]，[3, 0]，[0, 3]，[3]。

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

  • temp := 一個空字典
  • temp[0] := 1
  • s := 0
  • ans := 0
  • for i in range 0 to nums 的大小，執行
    • s := s + nums[i]
    • comp := s - target
    • 如果 comp 在 temp 中，則
      • ans := ans + temp[comp]
    • temp[s] := temp[s] + 1
  • 返回 ans

讓我們看一下以下實現以更好地理解

示例程式碼

線上演示

from collections import defaultdict

class Solution:
   def solve(self, nums, target):
      temp = defaultdict(int)
      temp[0] = 1
      s = 0
      ans = 0
      for i in range(len(nums)):
         s += nums[i]
         comp = s - target
         if comp in temp:
            ans += temp[comp]
            temp[s] += 1
         return ans

ob = Solution()
nums = [3, 0, 3]
target = 3
print(ob.solve(nums, target))

輸入

[3, 0, 3], 3

輸出

4

更新於: 2020年11月25日

437 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告