arrays - 浮点数的连续子数组求和到整数算法

假设我们有一个大小为n的数组a，则有n个未排序的浮点数。我们想找到一个连续的子数组B，使得B和为整数假设我们可以以o（1）为代价使用floor函数。注意，如果存在这样的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）中有这样做的方法吗？

最佳答案

如果我们忽略浮点计算误差，那么我们可以把分数的运行总和映射到一个地图，并检查相同的分数是否存在两次-（接近）O（n）的方法。
考虑到精度问题，我们可以对分数进行排序（或者像rb-tree一样将分数放入排序后的容器中），得到最小差分o（nlogn）方法。