有没有一种算法可以找到子列表的数量，使它们的总和小于给定的K？比O（N^2）更好。

Question

例子：

Sublists where sum is smaller than given K (K is the maximum sum).
[-1, 1, -2, 1, -1,]
N = -1

[-1, 1, -2]
[-2]
[-2, 1, -1]
[-1, 1, -2, 1, -1]

有4个它们。

我已经找到了相关的算法，但是他们只覆盖了非负数。

谢谢。

(示例：https://www.geeksforgeeks.org/number-subarrays-sum-less-k/ 这就是我需要的，但是那里的算法不能处理负数)

- Ondřej Baštař

---

我考虑过这个，但我需要一个比O(n^2)更好的算法，至少是O(n logn)。可能应该在问题中说明。 - Ondřej Baštař

我认为这是不可能的。效率是通过知道总和只能增加，所以一旦达到L限制，就可以停止搜索来实现的。但是，如果由于有负数而消失了这种可能性，则无法使用此优化。想象一下，如果最后一个数字是类似于-(MAX(ABS(list_n-1))+L)*len(list)的东西，那么所有子列表都将是有效的，因为最后一个元素将超过其前任的任何总和。而且你只有在检查所有元素的所有子列表时才会知道这一点——这是O(N^2)。 - LSerni

@chepner，问题只要求子列表-即连续子序列-而不是所有子集。 子列表有平方级别的数量。 输出是一个整数。 - kaya3

探索的想法：计算所有k≤n的前k个和。通过归并排序按这些总和对数组进行排序，同时计算逆序对（并将原始索引与总和相关联）。有效答案是满足差小于n的逆序对和非逆序对的索引。待定如何避免重复计算满足差小于n的逆序对？ - Dave

我认为 [-1, -1], [-2, -1] 也是这样的子集。 - Geeocode

Answer 1

让原始数组为 A，并创建一个累积和数组 S，使得S[i] = A 的前i个元素的总和。请注意，S 比A多一个元素。

现在，对于从A [i]到A [j]的每个子列表，其元素的总和为S [j + 1]-S [i]。

要获得答案，我们只需要计算具有i

您可以使用顺序统计树 (order statistic tree) 实现这一点: https://en.wikipedia.org/wiki/Order_statistic_tree 这是一棵带有每个子树大小记录的二叉搜索树，它允许您以 O(log N) 时间回答类似“有多少条目的值<=x”的问题。

从空树开始，然后：

for j=1 to S.length-1:
    add S[j-1] to the tree
    query for the number of elements in the tree with values > S[j] - K
    add that count to the total

总复杂度是O(N log N)(其中N是输入的大小！)，由于每个j在树中进行的O(log N)添加和查询操作而被支配。

- Matt Timmermans

---

我认为应该是 > S[j] - N。 - yassin

此外，在运行时的考虑中，使用 N 作为额外输入和输入大小似乎是不明智的。 - yassin

@yassin 谢谢。已更正。关于 N，是的，但你知道我的意思，我认为 OP 也是这样做的。 - Matt Timmermans

我认为这是正确的答案，如果我确认了，我会尝试将其标记为答案。我还将编辑我的问题，将N更改为K，因为这可能会令人困惑。 - Ondřej Baštař

Answer 2

如果您的列表包含负数，则无法在不对每个成员求和的情况下了解它们的总和。

- Ari Fordsham

---

“对每个成员求和”到底是什么意思，为什么它会导致复杂度大于O（N）？ - Matt Timmermans