1

例子：

给定一个随机数列表[1,5,1,1,3,10,5,4,2,1]、测试元素N=10 at index 5和一个MIN=20.

10包含a的最短子列表total>20显然是[3,10,5,4]带有 atotal=22和 a的列表size=4。

问题：

以有效方式找到这样一个子列表的算法是什么？

编辑：

  1. 可能存在满足“最短”条件的不同子列表。和一个有效的结果[10,5,4,2]一样短。[3,10,5,4]

  2. 此问题中的“子列表”是原始列表的连续项目块。[5,10,5,4]不是有效的子列表（我将其称为子集）。

4

2 回答 2

1

以下算法应该是 O(n)：

从测试元素开始向左添加元素，直到总和> = min。这给出了对子列表长度 l 的第一个猜测（从索引 i 开始）。不增加长度为 l 的子列表的起始索引 i 每一步（直到你到达你的测试元素）和每一步测试如果你可以将子列表缩短一（在右边，即减少长度 l）而不变得小于 min。

注意边缘情况：左边的总和不够大或总和不够大。

于 2011-03-04T15:27:35.813 回答
0

查找最短子列表 > MAX 与查找最短子列表 <= MAX 相同，如果添加了之前或之后的项目，则子列表的总数超过 MAX： 使用[1,5,1,1,3,10,5,4,2,1]and MAX=20，[1,3,10]是一个子列表，包括10但自添加下一个后无效5总共给出19 < MAX. 第一个有效的子列表在这里[5,1,1,3,10]。

算法：

  1. marker为找到的最短子列表的长度创建一个。
  2. 创建游标left和right.
  3. 将两个光标设置为N。
  4. left向左移动while total(at left, ..., at N) <= MAX或left = 0。
    1. 如果left > 0存储n - left + 1在marker. 转到 6。
  5. right向右移动while total(at left, ..., at right) <= MAX或right = list.size - 1。
    1. 如果right < list.size - 1存储right - left + 1在marker.
    2. 否则：返回list.size。
  6. 循环while left < N and right < list.size - 1：
    1. left向右移动一位。
    2. 测试项目at right + 1，如果有的话。
      1. 如果total + at right + 1 > MAX存储right - left + 1在marker.
      2. 否则向右移动一个。

无论如何，我会给霍华德答案。

于 2011-03-08T07:33:20.643 回答