给定一个数组(假设非负整数),我们需要找到最小长度子集,使得元素之和不小于K.K是另一个作为输入提供的整数.
是否有可能得到时间复杂度为O(n)[n的大哦]的解决方案？
我目前的想法是以下几行:我们可以在O(n*log n)中对数组进行排序,然后从最大数字开始迭代排序数组并保持运行总和,直到运行总和变为> = K.
但是,这将具有O(n*(log n + 1))的最差情况运行时间.
所以如果有人能在O(n)时间分享这样做的想法,我真的很感激..
注意:在此上下文中,子数组的元素不必是原始数组的连续序列
这似乎是动态规划的一个问题。构建数组时，会构建另一个包含每个特定索引的累积总和的数组。所以i该数组中的每个都有来自 的总和1..i。
现在很容易看出索引值的总和p..q是SUM(q) - SUM(p-1)（特殊情况SUM(0)是0）。显然我在这里使用了基于 1 的索引......这个操作是 O(1)，所以现在你只需要一个 O(n) 算法来找到最好的一个。
一个简单的解决方案是跟踪 ap并q在数组中遍历它们。你q开始扩展。然后你反复收缩p和扩张q，就像毛毛虫在你的阵列中爬行一样。
扩展q：
p <- 1
q <- 1
while SUM(q) - SUM(p-1) < K
q <- q + 1
end while
现在q位于子数组和刚刚超过（或等于）的位置K。子数组的长度为q - p + 1。
在q循环之后，您测试子数组长度是否小于您当前的最佳长度。然后您前进一步p（这样您就不会意外跳过最佳解决方案）并再次前进。
你真的不需要创建SUM数组......你可以在你去的时候构建子数组总和......你需要回到使用'真实'p而不是之前的那个。
subsum <- VAL(1)
p <- 1
q <- 1
while q <= N
-- Expand
while q < N and subsum < K
q <- q + 1
subsum <- subsum + VAL(q)
end while
-- Check the length against our current best
len <- q - p + 1
if len < bestlen
...
end if
-- Contract
subsum <- subsum - VAL(p)
p <- p + 1
end while
笔记：
j_random_hacker 说：这将有助于准确解释为什么只检查该算法检查的 O(n) 个不同子数组而不是所有 O(n^2) 个可能的不同子数组是可以接受的
动态规划的理念是：
在这种情况下(p,q)，p <= q通过对元素求和来计算单个解决方案候选（一些这样的）。因为这些元素是正整数，我们知道对于任何候选(p,q)解，候选解(p,q+1)都会更大。
所以我们知道如果(p,q)是最小解，那么(p,q+1)就不是。一旦有了候选人，我们就结束搜索，并测试该候选人是否比我们目前看到的任何候选人都好。这意味着对于每个p，我们只需要测试一个候选人。这导致两者p并且q只会不断增加，因此搜索是线性的。
另一部分（使用以前的解决方案）来自于认识到这一点，sum(p,q+1) = sum(p,q) + X(q+1)并且类似地sum(p+1,q) = sum(p,q) - X(p)。因此，我们不必对每一步之间p和q每一步的所有元素求和。每当我们前进搜索指针之一时，我们只需添加或减去一个值。
希望有帮助。
有一个线性时间算法可以找到K个最大的数字 - http://en.wikipedia.org/wiki/Selection_algorithm.当然你想要的只是足够的最大数字,总计至少K.
在标准选择算法中,您采用随机轴,然后查看每侧有多少个数字.然后你接受或拒绝一半,继续工作另一半.您只是依次查看每一半中的每个数字 - 每个枢轴阶段的成本是线性的,但每个阶段考虑的数据量减少得足够快,总成本仍然只是线性的.
如果您获取枢轴上方所有数字的总和,则枢轴平台的成本仍然只是线性的.利用这一点,你可以工作,如果与之前选择的任何号码接受所有这些数字,在一起,会给你,加起来至少K.如果是这样,你可以抛弃其他数字号码的收集和使用上面的号码下一次通过的枢轴.如果没有,您可以接受枢轴上方的所有数字,并使用枢轴下方的数字进行下一次传递.与选择算法一样,枢轴本身和任何关系都会为您提供一些特殊情况以及尽早找到确切答案的可能性.
(所以我认为你可以使用在你看看枢轴之上的数字之和选择算法的修改版本中(随机)线性时间做到这一点,而不是有多少数字是枢轴之上.