学步园

/*
2)一串首尾相连的珠子(m)，有N种颜色(N<=10)，
设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。
并分析时间复杂度与空间复杂度。

*/
#include<iostream>
#include<stdio.h>
using namespace std;

int shortFullColor(int a[], int n, int m) 
{
	
	int color[10],colorNum=m;// 记录颜色总数 
	int ss=0,kk=0;//2个移动的指针 
	int min=n;
	
	memset(color,0,sizeof(color));
	while(1)
	{	
		while(colorNum>0&&ss<n)//一直找到颜色都有为止 
		{
			if(color[a[ss]]==0) colorNum--;//这个颜色还未存在，找到一个新颜色 
				color[a[ss]]++;
				ss++;
			//	printf("%d",colorNum);
		}
		
		while(1)
		{
			color[a[kk]]--;
			if(color[a[kk]]==0)//该颜色就这一种，获取整个长度 
				break;
			kk++;//颜色不止一种，向后移动，可以不要当前位置 
		}
		if(min>ss-kk)
			min=ss-kk;
			 
		kk++;//当前KK的颜色减去，从下个位置开始，查找减去的颜色 
		colorNum++;// 减去的颜色，要重新查找 
		
		if(ss>=n) 
			return min;
		}
}

int main()
{
	int a[]={1,2,3,3,2,5,2,1,3,3,4,5,4,6};//数字相同代表相同颜色珠子 
	int ans;
	
	ans=shortFullColor(a,14,4);//4 查找4种颜色不同珠子5,2,1,3
	printf("%d\n",ans);
	
	ans=shortFullColor(a,14,5);//6 查找5种颜色不同珠子5,2,1,3,3,4
	printf("%d\n",ans);
	
	ans=shortFullColor(a,14,6);//8 查找6种颜色不同珠子2,1,3,3,4,5,4,6
	printf("%d\n",ans);
}