题目

最近自走棋非常的火爆，无论是英雄联盟、王者荣耀都推出了自走棋的玩法，玩过自走棋的朋友的知道，一场比赛下来能不能赢，跟抽到的牌的关系非常的大。沙茶敏非常喜欢玩骑士流，他想收集所有的骑士，这里不得不引申出一个问题，在一个连续的序列里面，沙茶敏要想收集所有的不同类型的骑士，最小的区间是多少呢？大家来帮忙想出一个算法。

样例

我们用一个例子还解释这个问题，假如这个序列有7张牌，总共有ABC3种不同的骑士，假设牌的序列位ABAACCB，那么要收集所有的不同总类的骑士，最小的区间是BAAC，长度为4。

分析

这个题目，我们不难想到一个最简单的算法。我们可以使用穷举法，穷举出所有的区间，然后判断里面是否拥有所有的牌，如果是，那么就看看是否比之前的区间更小，更新正确答案。我们不难写出伪代码。

穷举左区间的算法时间复杂度为O(N)，穷举出右区间的算法复杂度为O(N)，判断是否拥有所有骑士的算法复杂度为O(N)，整体算法复杂度为O(N^3)。

优化

很显然，我们进行了很多次没有必要的操作。例如，在上述算法中，我们统计了[2,5],[2,6]这两个区间的时候，是否有重复计算呢？假如我们统计[2,5]这样一个区间的时候，再多统计第6位，不就统计了[2,6]区间了么，不就避免了重复计算？

所以我们只需要枚举出左节点，然后从右边一直寻找，直到满足所有骑士，这样的时间复杂度为O(N^2)。

再优化

我们再进一步去思考，在上述优化算法中，我们统计[2,6]区间与[3,6]区间，是否也是有同样的重复计算呢？假如我们能够再减少重复计算，岂不是更好！那么，到底有没有办法减少重复的计算呢？

我们举个例子，还是上面的ABAACCB，第一位是A，第二位是B，这个时候区间是[1,2]，这个时候我们计算第三位，发现第三位是A，这个时候，第一位的A是不是没有存在的意义了？因为这个区间里面已经有另外一个A了，所以本来区间是[1,3]，我们可以把第1位踢出去，变成[2,3]。就这样，我们每次往后走一步，都要判断前面的是否能够踢出去，我们通过一个图片来看一下这个流程。

就这样，我们把绿色的部分当成一个队列，我们每次走下一步，就将新的元素入队，再判断最前面的是否有重复的，如果重复，那么就把它踢出队列，就这样，每一个元素最多入队一次，总共的算法时间复杂度位O(N)。

总结

算法优化的精髓之一在于减少重复计算，我们对这个并不陌生，想想用一个数组来存斐波那楔数列的计算结果就是用这种思想，这个题目中，我们将有用的区间只计算一次，这种使用一个队列，不停的队尾入队，队首出队的方法，我们也称之为尺卷法。欢迎大家关注我，共同学习，共同进步。大家的支持是我继续唠嗑的动力。同名公众号（沙茶敏碎碎念）

（正文已结束）

免责声明及提醒：此文内容为本网所转载企业宣传资讯，该相关信息仅为宣传及传递更多信息之目的，不代表本网站观点，文章真实性请浏览者慎重核实！任何投资加盟均有风险，提醒广大民众投资需谨慎！