Непрерывный подмассив чисел с плавающей запятой суммируется с целочисленным алгоритмом

Question

Предположим, у нас есть массив A размером n, а 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

Если мы игнорируем ошибки вычисления с плавающей запятой, тогда мы можем поместить дробные части текущих сумм в карту и проверить, существует ли одна и та же дробь дважды - (близко к) подходу O (n).

Учитывая проблемы точности, мы можем сортировать дроби (или помещать их в отсортированный контейнер, такой как дерево RB) и получать наименьшее различие - подход O (nlogn)