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

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

如果忽略浮点计算错误，则可以将fractional部分运行总和放入地图中，并检查相同的分数是否存在两次-（接近）O（n）方法。

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