浮点数的连续子数组与整数算法的总和

Question

假设我们有一个大小为 n 的数组 A，有 n 个未排序的浮点数。我们想找到一个连续的子数组 B，使得 B 的总和为一个整数。假设我们可以以 O(1( 为代价使用楼层函数。请注意，如果存在这样的 B，我们需要返回 B。 我的想法：

rsum = running sum of A(i.e. rsum[i]=A[1]+A[2]+...+A[i])
for i from 1 to n:
for j from i to n:
e = rsum[j]-rsum[i]+A[i]
if e==floor(e)
return A[i....j]
return "no such subarray"

这是一个 O(n^2( 算法，有没有办法在 o(n^2( 中做到这一点？

Answer 1

如果我们忽略浮点计算误差，那么我们可以将运行总和的小数部分放入映射中，并检查相同的分数是否存在两次 - (接近(O(n( 方法。

考虑到精度问题，我们可以对分数进行排序(或将它们放入像RB树这样的排序容器中(并获得最小的差异 - O(nlogn(方法