数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找和至少为目标值的最小子列表的大小
假设我们有一个名为 nums 的数字列表，以及另一个名为 target 的输入，我们需要找到最短子列表的大小，使得其总和等于或大于 target。如果不存在这样的子列表，则返回 -1。
因此，如果输入类似于 nums = [2, 11, -4, 17, 4] target = 19，则输出将为 2，因为我们可以选择 [17, 4] 使得总和至少为 19。
为了解决这个问题，我们将遵循以下步骤：
ps := 一个仅包含一个元素 0 的列表
对于 nums 中的每个数字 num，执行以下操作：
在 ps 后插入 (ps 的最后一个元素 + num)
如果 num >= target，则
返回 1
min_size := 无穷大
q := [0]
j := 0
对于范围从 1 到 ps 大小的 i，执行以下操作：
j := j 和 q 大小 - 1 的最小值
当 j < q 大小 且 ps[i] - ps[q[j]] >= target 时，执行以下操作：
min_size := min_size 和 (i - q[j]) 的最小值
j := j + 1
当 q 不为空 且 ps[i] <= ps[q 的最后一个元素] 时，执行以下操作：
从 q 中删除最后一个元素
在 q 的末尾插入 i
如果 min_size < 无穷大，则返回 min_size，否则返回 -1
示例
让我们查看以下实现以更好地理解：
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))输入
[2, 11, -4, 17, 4], 19
输出
2
更新于： 2020-12-23
149 次浏览
广告