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

-2

问题是 - 给出一个大小为n和数字S的整数数组。您必须找到总和为的最小集合的连续整数比S.如果没有这样的组存在的数量，输入0找到其总和大于给定整数的最小整数集合

空间复杂度O（1）时间复杂-O（n）的

例 -

阵列A = {2时， 5,4,6,3,9,2,17,1}

S = 1 7

输出= 2

Explanation-

可能的解决方案是： -

{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。

我的尝试 - 我在O（n^2）时间复杂度中解决了这个问题。有没有办法通过迭代阵列来进一步优化它，并将复杂度降至O（n）？

不需要整个代码。只要基本逻辑的基本思想就足够了。谢谢。

来源

2016-11-05 Code_maniac

任何尝试独立解决这个问题？ – dasblinkenlight

我投票结束这个问题作为题外话，因为堆栈溢出不做你的功课。 – David

我用时间复杂度O（n^2）解决了它，但我无法进一步优化它。这个问题可以通过O（n）时间复杂度解决，而不需要使用额外的数组。 –

假设所有的整数都是非负和小号是肯定的，你可以使用下面的算法：

使用两个指标，一个是当前序列开始的地方，另一个是它的结束位置。当该序列的总和太小时，可以通过递增第二个索引来扩展序列;如果总和超过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）作为倍，在内部循环的语句执行的总数是从不超过Ñ（我每次递增，并且永远不会绕过Ĵ）。

来源

2016-11-05 12:28:30 trincot

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

回答

相关问题