在 O(n) 中的已排序双向链表中查找具有给定平均值的最长子列表
Find longest sublist with given average in sorted doubly linked list in O(n)
给定一个数字和一个排序的双向链表（数据为整数），我必须在 O(n) 中找到平均为给定数字的最长子列表。
你会怎么做？
首先，您找到所有索引的累计和。假设这是一个数组，cumsum[1..n]
现在，从两个指针开始，一个指向第一个节点，一个指向最后一个节点。计算此范围的平均值为 (cumsum[last]-cumsum[first])/(last-first+1)。如果这大于目标平均值（比如 k），则向内移动向后指针，因为这总是会减少平均值（因为它已排序）。同样，如果avg < k，将前指针向前移动。这样你要么得到一个平均 k 的范围，如果它存在，要么意识到如果前后指针交叉，这样的 k 不存在。由于我们在每一步中至少移动了一个指针，所以这是 O(n)。
给定一个数字和一个排序的双向链表（数据为整数），我必须在 O(n) 中找到平均为给定数字的最长子列表。 你会怎么做？
首先，您找到所有索引的累计和。假设这是一个数组，cumsum[1..n]
现在，从两个指针开始，一个指向第一个节点，一个指向最后一个节点。计算此范围的平均值为 (cumsum[last]-cumsum[first])/(last-first+1)。如果这大于目标平均值（比如 k），则向内移动向后指针，因为这总是会减少平均值（因为它已排序）。同样，如果avg < k，将前指针向前移动。这样你要么得到一个平均 k 的范围，如果它存在，要么意识到如果前后指针交叉，这样的 k 不存在。由于我们在每一步中至少移动了一个指针，所以这是 O(n)。