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 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告