java - 在 O(n) 的有序双向链表中查找具有给定平均值的最长子列表

Question

给定一个数字和一个排序的双向链表(数据为整数)，我必须找到最长的子列表，其平均值是给定数字的 O(n) 时间复杂度。你会怎样做呢？

Answer 1

首先，找到所有索引的累积和。假设这是一个数组，cumsum[1..n]

现在，从两个指针开始，一个指向第一个节点，一个指向最后一个节点。计算该范围的平均值为 (cumsum[last]-cumsum[first])/(last-first+1) 。如果这大于目标平均值(例如 k )，则向内移动后向指针，因为这总是会减少平均值(因为它已排序)。同样，如果 avg < k ，向前移动前指针。这样，您要么最终得到一个具有平均 k 的范围(如果存在)，要么意识到如果前指针和后指针交叉，这样的 k 不存在。由于我们在每一步中至少移动一个指针，因此时间复杂度为 O(n)。