示例:
[-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/这是我需要的,但是该算法不适用于负数)
如果您的列表包含负数,则不对每个成员求和就不可能知道它们的总和。
是,有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
,然后输出。