程序查找最小子列表的大小，该子列表的总和至少是Python中的目标

Z时代
2024-01-10
分类：综合

假设我们有一个称为nums的数字列表，另一个名为target的输入，我们必须找到最短子列表的大小，以使其总和等于target或更大。如果没有这样的子列表，则返回-1。

因此，如果输入类似于nums = [2，11，-4，17，4] target = 19，则输出将为2，因为我们可以选择[17，4]以获得至少19的总和。

在线示例

让我们看下面的实现以更好地理解-

class Solution:
   def solve(self, nums, target):
      ps = [0]
      for num in nums:
         ps += [ps[-1] + num]
         if num >= target:
            return 1
         min_size = float("inf")
         q = [0]
         j = 0
         for i in range(1, len(ps)):
            j = min(j, len(q) - 1)
            while j < len(q) and ps[i] - ps[q[j]] >= target:
               min_size = min(min_size, i - q[j])
               j += 1
            while q and ps[i] <= ps[q[-1]]:
               q.pop()
            q.append(i)
         return min_size if min_size < float("inf") else -1
ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))