算法-sliding window 实例

1. Sliding Window

找出通用子数列（给定数列包含“2”，“4”如“【2，2，4，4，2，4，4】）

一个通用子数列满足以下两个条件

一：子数列是连续的，即从原数列里按顺序取出的子集合)，eg.

[2],[2],[4],[4],[2],[4],[4],[2,2],[2,4],[4,4]…[2,2,4],[2,4,4],等，[2,4,4,2]就不属于这类，因为“2”不连续在一起。

二：子数列中“2”与“4”的个数是相同的：24，42，2244，24,这类属于universal subarray.

写一个函数根据传递的array找到对应universal array的个数。

分析：

这是一个典型的sliding window类型的题,下图是我们的整体思路，初始化一个sliding window， from 指针为0，to 指针为-1,代表最初的sliding window为空，endofsliding=0 代表起始的sliding window里最后一个元素为0，这里可以设置为任何不为2或4的元素，segement代表sliding window里的数字片段，如22，2，222，连续相同的数字为一个片段，不同的数字加入，且加入的数字和sliding window的最后一个元素endofsliding不同的时候片段segement自增，初始化一个长度为2的数组，分别用于存储2或4在sliding window里的个数，我们的slidingwindow设置为扩张到两个片段且下一个元素与sliding window的endofsliding不一样时停止，此时一个sliding window扩张完毕，我们可以对第一个sliding window计算universal array的个数里，不难发现，一个sliding window里的universal array的个数与这个window里出现的字符个数次数最小的字符的个数相同，ru

24->1,224->1,2244->2,22444->2,且我们对这个sliding

window计算universal array的个数实际上是对这个sliding里的包含第一个片段的可能的universal array个数，于是乎，当我们计数完毕后，我们应该将第一个片段的数字都抛出这个sliding window，将slidingwindow的片段缩减到1，将from 前移至下一个片段，然后再次扩张slidingwindow，至sliding window的segement 再次为2，再次计算接下来的通用数组个数，以此类推，直至整个数组遍历完毕。

根据上面的分析可以写出这样的代码：

Class CountUniversalArray{

        Int segment,from,to,end,total;

        Int [] arr;

        Int   countUniversalArrayNumber(int [] array){

               Segment= 0; from=0;to=-1;end=0; total=0;

               arr =new int[2];

               list =array;

               while(expand()){

       shrink();

}

    Booleanexpand(){

//扩张条件是to 要小于数组index最大，即length-1; segment不能//大于2，或者是已经为2了，但是sliding的最后一个元素与下一个//数组元素相等时还能扩张：

       while((segment<2|| (segment ==2 && end == list.get(to+1))) && to

       to++;

//获取当前的数组元素：

       Intn = list.get[to]；

       Intj = n==2?0:1;

Arr[j]++;

If(end != n){

Segment++;

End = n;

}

}

Total += Math.min(arr[0],arr[1]);

Return segment == 2;

}

Void shrink(){

       While(from

              Int k = list.get(from)==2?0:1;

       from ++;

       arr[k]--;

       if(arr[k] ==0){

       seg--;

}

}

}

}

}