算法 – 如何找到包含序列的所有元素的最小长度子序列

算法：

首先,确定阵列中不同元素的数量 – 这可以在线性时间内轻松完成.让有不同的元素.

分配大小为10 ^ 5的数组cur,每个数组cur显示当前子序列中使用的每个元素的数量(见后文).

持有一个cnt变量,显示在考虑的序列中当前有多少个不同的元素.现在,采用两个索引,以下列方式开始和结束数组：

>初始化cnt并开始为0,结束为-1(第一次增量后为0).然后尽可能执行如下：

>如果cnt！= k：

2.1.增量结束.如果end已经是数组的结尾,那么break.如果cur [array [end]]为零,则增加cnt.增量cur [array [end]].

其他：

2.2 {

尝试增加begin迭代器：while cur [array [begin]]> 1,递减它,并增加begin(cur [array [begin]]> 1意味着我们在我们当前的子序列中有另一个这样的元素).毕竟,将[开始,结束]间隔与当前答案进行比较,如果它更好,存储它.

}

在进一步的过程变得不可能之后,你得到了答案.复杂度是O(n) – 只是通过数组中的两个Interator.

执行C：

#include <iostream>

using namespace std;

const int MAXSIZE = 10000;

int arr[ MAXSIZE ];
int cur[ MAXSIZE ];

int main ()
{
   int n; // the size of array
   // read n and the array

   cin >> n;
   for( int i = 0; i < n; ++i )
      cin >> arr[ i ];

   int k = 0;
   for( int i = 0; i < n; ++i )
   {
      if( cur[ arr[ i ] ] == 0 )
         ++k;
      ++cur[ arr[ i ] ];
   }

   // now k is the number of distinct elements

   memset( cur, 0, sizeof( cur )); // we need this array anew
   int begin = 0, end = -1; // to make it 0 after first increment
   int best = -1; // best answer currently found
   int ansbegin, ansend; // interval of the best answer currently found
   int cnt = 0; // distinct elements in current subsequence

   while(1)
   {
      if( cnt < k )
      {
         ++end;
         if( end == n )
            break;
         if( cur[ arr[ end ]] == 0 )
            ++cnt; // this elements wasn't present in current subsequence;
         ++cur[ arr[ end ]];
         continue;
      }
      // if we're here it means that [begin, end] interval contains all distinct elements
      // try to shrink it from behind
      while( cur[ arr[ begin ]] > 1 ) // we have another such element later in the subsequence
      {
         --cur[ arr[ begin ]];
         ++begin;
      }
      // now, compare [begin, end] with the best answer found yet
      if( best == -1 || end - begin < best )
      {
         best = end - begin;
         ansbegin = begin;
         ansend = end;
      }
      // now increment the begin iterator to make cur < k and begin increasing the end iterator again
      --cur[ arr[ begin]];
      ++begin;
      --cnt;
   }

   // output the [ansbegin, ansend] interval as it's the answer to the problem

   cout << ansbegin << ' ' << ansend << endl;
   for( int i = ansbegin; i <= ansend; ++i )
      cout << arr[ i ] << ' ';
   cout << endl;

   return 0;
}