假设我们有一个大小为 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) 中做到这一点？
最佳答案
如果我们忽略浮点计算错误，那么我们可以将运行总和的分数部分放入映射中，并检查是否存在两次相同的分数 -(接近)O(n) 方法。
考虑到精度问题，我们可以对分数进行排序(或者像RB树一样将它们放入排序的容器中)并得到最小的差异——O(nlogn)方法
关于arrays - float 的连续子数组求和为整数算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58491386/