arrays - float 的连续子数组求和为整数算法

Question

假设我们有一个大小为 n 的数组 A，其中有 n 个未排序的 float 。我们想要找到一个连续的子数组 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) 中做到这一点？

Answer 1

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

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