是否有一种算法可以找到总数小于N的子列表?比O(N ^ 2)

问题描述 投票:2回答:1

示例:

[-1, 1, -2, 1, -1,]
sublists where sum is smaller than N.
[-1, 1, -2]
[-2]
[-2, 1, -1]
[-1, 1, -2, 1, -1]

其中有四个。

我已经找到了用于此的算法,但它们只涵盖了非负数。

谢谢。

((示例:https://www.geeksforgeeks.org/number-subarrays-sum-less-k/这是我需要的,但是该算法不适用于负数)

python algorithm data-structures
1个回答
0
投票

如果您的列表包含负数,则不对每个成员求和就不可能知道它们的总和。


0
投票

是,有O(n)解决方案:https://www.geeksforgeeks.org/number-subarrays-sum-less-k/

您可以执行以下操作以使其适用于负整数:

First pass:查找列表中所有元素的最小值,例如min_val。取另一个变量min_offset = min(min_val, 0)。 (花费O(n)时间)

第二遍:min_offset的负数添加到列表中的每个元素以及要与之比较子数组的元素k中。

arr = arr - min_offset
k = k - min_offset

(再次花费O(n)时间)

第三遍:运行可用于此处的非负整数的算法:https://www.geeksforgeeks.org/number-subarrays-sum-less-k/。 (算法本身就是O(n)。)>

因此,您来到一个O(n)空间的O(1)解决方案。请注意,您仅在计算小于值k的子数组的数量。为了输出子数组,您需要从所有元素中减去min_offset,然后输出。

© www.soinside.com 2019 - 2024. All rights reserved.