找到总和大于给定整数的最小整数集

Question

我试图解决以下问题。我在O（n ^ 2）时间复杂度中解决了这个问题。有没有办法进一步优化它并通过迭代数组一次将复杂性降低到O（n）？

给定一个n个整数和一个数字S的数组。我需要找到总和大于数字S的最小连续整数集。如果不存在这样的集合，我将打印0。

所需的复杂性：空间复杂度-O（1）时间复杂度-O（n）

例-

数组A = {2,5,4,6,3,9,2,17,1}

S = 17

输出= 2

说明-

可能的解决方案是： -

{2,5,4,6,3} = 2 + 5 + 4 + 6 + 3 = 20（> 18）= 5个数字

{5,4,6,3,9} = 27（> 18）= 5个数字

{4,6,3,9} = 22（> 18）-4个数字

{6,3,9,2} = 20 = 4个数字

{3,9,2,17} = 4个数字

{9,2,17} = 3个数字

{2,17} = 2个数字

所以，最小= 2个数字。输出= 2。

Answer 1

假设所有整数都是非负数且S为正数，则可以使用以下算法：

使用两个索引，一个用于当前序列的开始，另一个用于结束的位置。当该序列的总和太小时，通过递增第二个索引来扩展序列;如果总和超过S，则通过递增第一个索引来跟踪它是否是最好的，同时从序列中删除第一个值。

这是更正式的伪代码中的算法：

n = size(A)
best = n + 1
sum = 0
i = 0

for j = 0 to n - 1:
    sum = sum + A[j]
    while sum > S:
        if j - i + 1 < best:
            best = j - i + 1
        sum = sum - A[i]
        i = i + 1

if best > n:
    best = 0

output best

空间复杂度为O（1），因为涉及4个数值变量（不计算输入数组），它代表固定数量的内存。

时间复杂度是O（n），因为内循环中的语句执行的总次数绝不会超过n（i每次递增并且永远不会绕过j）。