m个珠子共n种颜色，找出包含n种颜色的最短连续片段（百度面试题）

本文主要是介绍m个珠子共n种颜色，找出包含n种颜色的最短连续片段（百度面试题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题有很多变种，先考虑最简单的情况，m个珠子排成一行（不成环），求包含n种颜色的最短连续片段。可以将题目抽象成有一个数组a，大小为m。数组a里的每个元素的取值范围是[1，n]（表示n种颜色），那么求数组a中包含[1，n]所有整数的最短的序列的长度。

比如m=11，n=3的情况

数组a

数组a的坐标	1	2	3	4	5	6	7	8	9	10	11
数组a的颜色值	1	2	2	1	1	3	2	2	3	2	3

解法一：暴力法，这是最容易想到，并且简单的方法。

算法描述：从数组a的坐标1开始逐个向后检查，直到包含了所有的颜色值（3个），记录下连续片段的长度len，然后再从数组a的坐标2开始检查……

这个算法的时间复杂度是O（N2）。

解法二：新申请一个数组b，大小为3（颜色值的个数）并初始化为0。数组b[i]的值是颜色值为i的元素出现的次数。

算法描述：设置两个指针p1和p2，p1和p2开始时指向a数组中第一个元素，然后令b[a[1]]=1，然后p2开始向后走，检查下一个坐标的元素的值，比如下一个元素是a[2]，a[2]=1，那么就设置b[a[2]]+=1，也就是b[1]+=1.直到b数组中所有的元素都不为0时，就说明p1到p2之间所有的元素已经包含了所有的三种颜色。此时记录下长度len=p2-p1. 然后指针p1将要往后移动，移动之前，要将p1指向的元素在颜色数组中去掉，也就是b[*p1]-=1，如果b的元素减1以后变为了0，就说明现在p1和p2之间少了一种颜色。所以p2要继续向后移动，来保证b数组中任意一个元素都大于0. 直到最后p2指针指向了数组的末尾，算法结束。

此算法只扫描一遍数组a即可，整体看时间复杂度为O(N)。

//令数组a和数组b的坐标都从1开始
int leastLength(int a[12])
{
   int length;
   int min = MAX_VALUE;
   int b[4];
   memset(b, 0, sizeof(b));
   int *p1 = a;
   int *p2 = a;
   while(p2 < &a[12])
   {
      while(数组b中有0 && p2 <= &a[12])
     {
        b[*p2]+=1;
        p2++;
     }
     while(数组b中没有0)
     {
        b[*p1]-=1;
        p1++;
     }
     if(p2 <= &a[12])
     {
       length = p2-p1+2;
       if(length < min)
       {
          min = length;
       }
     }
     else
       return min;
   }
   return min;
}