浮点数的连续子数组求和为整数算法
Contiguous subarray of floating numbers sums to integer algorithm
假设我们有一个大小为n的数组A，其中有n个未排序的浮点数。我们想要找到一个连续的子数组 B，使得 B 和为整数。假设我们可以以 O(1) 为代价使用 floor 函数。请注意，如果存在这样的 B，我们需要 return 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) 中做到这一点？
如果我们忽略浮点计算错误，那么我们可以将运行总和的小数部分放到一个map中，检查是否存在两次相同的小数-（关闭到) O(n) 方法。
考虑到精度问题，我们可以对分数进行排序（或者像RB树一样将它们放入排序的容器中）并得到最小的差异 - O(nlogn) 方法
假设我们有一个大小为n的数组A，其中有n个未排序的浮点数。我们想要找到一个连续的子数组 B，使得 B 和为整数。假设我们可以以 O(1) 为代价使用 floor 函数。请注意，如果存在这样的 B，我们需要 return 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) 中做到这一点？
如果我们忽略浮点计算错误，那么我们可以将运行总和的小数部分放到一个map中，检查是否存在两次相同的小数-（关闭到) O(n) 方法。
考虑到精度问题，我们可以对分数进行排序（或者像RB树一样将它们放入排序的容器中）并得到最小的差异 - O(nlogn) 方法