问题描述
给定一个整数数组和一个范围(低、高),找出所有数组中的连续子序列,其总和在范围内.
有没有比 O(n^2) 更好的解决方案?
Is there a solution better than O(n^2)?
我尝试了很多,但找不到比 O(n^2) 更好的解决方案.请帮我找到更好的解决方案或确认这是我们能做的最好的.
I tried a lot but couldn't find a solution that does better than O(n^2). Please help me find a better solution or confirm that this is the best we can do.
这就是我现在所拥有的,我假设要定义为 [lo, hi]
的范围.
This is what I have right now, I'm assuming the range to be defined as [lo, hi]
.
public static int numOfCombinations(final int[] data, final int lo, final int hi, int beg, int end) {
int count = 0, sum = data[beg];
while (beg < data.length && end < data.length) {
if (sum > hi) {
break;
} else {
if (lo <= sum && sum <= hi) {
System.out.println("Range found: [" + beg + ", " + end + "]");
++count;
}
++end;
if (end < data.length) {
sum += data[end];
}
}
}
return count;
}
public static int numOfCombinations(final int[] data, final int lo, final int hi) {
int count = 0;
for (int i = 0; i < data.length; ++i) {
count += numOfCombinations(data, lo, hi, i, i);
}
return count;
}
推荐答案
O(n)时间解决方案:
您可以为问题的精确"版本扩展双指针"的想法.我们将维护变量 a
和 b
以使所有间隔为 xs[i,a), xs[i,a+1), ..., xs[i,b-1)
在搜索范围 [lo, hi]
中有一个总和.
You can extend the 'two pointer' idea for the 'exact' version of the problem. We will maintain variables a
and b
such that all intervals on the form xs[i,a), xs[i,a+1), ..., xs[i,b-1)
have a sum in the sought after range [lo, hi]
.
a, b = 0, 0
for i in range(n):
while a != (n+1) and sum(xs[i:a]) < lo:
a += 1
while b != (n+1) and sum(xs[i:b]) <= hi:
b += 1
for j in range(a, b):
print(xs[i:j])
这实际上是 O(n^2)
因为 sum
,但我们可以通过首先计算前缀和 ps
使得 ps[i] = sum(xs[:i])
.那么 sum(xs[i:j])
就是 ps[j]-ps[i]
.
This is actually O(n^2)
because of the sum
, but we can easily fix that by first calculating the prefix sums ps
such that ps[i] = sum(xs[:i])
. Then sum(xs[i:j])
is simply ps[j]-ps[i]
.
这是在 [2, 5, 1, 1, 2, 2, 3, 4, 8, 2]
上运行上述代码的示例,其中 [lo, hi]= [3, 6]
:
Here is an example of running the above code on [2, 5, 1, 1, 2, 2, 3, 4, 8, 2]
with [lo, hi] = [3, 6]
:
[5]
[5, 1]
[1, 1, 2]
[1, 1, 2, 2]
[1, 2]
[1, 2, 2]
[2, 2]
[2, 3]
[3]
[4]
这在时间 O(n + t)
中运行,其中 t
是输出的大小.正如一些人所注意到的,输出可以大到 t = n^2
,即如果所有连续的子序列都匹配.
This runs in time O(n + t)
, where t
is the size of the output. As some have noticed, the output can be as large as t = n^2
, namely if all contiguous subsequences are matched.
如果我们允许以压缩格式写入输出(输出对 a,b
,其中所有子序列都是连续的),我们可以获得纯 O(n)
时间算法.
If we allow writing the output in a compressed format (output pairs a,b
of which all subsequences are contiguous) we can get a pure O(n)
time algorithm.
这篇关于谷歌面试:在给定的整数数组中查找所有连续的子序列,其和在给定范围内.我们能比 O(n^2) 做得更好吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!