滑动窗口算法题目(滑动窗口算法图解)

今天上午做了摩根士丹利的一道笔试，之前面试的时候有做过类似的题目，其实比较简单，但是没有完全做出来。晚上debug了一下，发现自己写错了一个关键字，对相关知识点还是不是很熟悉，太难了！

一个班级有许多学生，每个学生都有特定的知识或才能。每个天赋都表示为从1到TalentCount的整数。必须为智力竞赛组成团队，并且必须至少有一名成员具有每个才能。人才被列在一个数组中，学生必须从任何元素索引位置开始连续选择。对于每个起始索引，确定必须选择的最少学生人数，以使每个人才至少有一个团队成员。如果不可能，则为该索引返回-1。

例子
人才数=3
人才=【1，2，3，2，1】

至少有3个学生可以拥有至少3个才能，以下长度为3或更大的子数组是可能的：
从位置1开始：【1，2，3】，【1，2，3，2】 【1，2，3，2，1】
从位置2开始：【2，3，2】，【2，3，2，1】
从位置3开始：【3，2，1】

从第一个位置开始，具有每个才能值的最短子数组的长度为3。
从元素2开始，最短的长度为4。
在位置3，最短且唯一可能的子数组的长度为3，少于3人的团队是不可能组成团队的，因此从最后两个位置开始的子序列将失效。

这里填写问题的分析：
其实这道题已经告诉我们的目的了，就是求具有每个才能值的最短子数组。
那么我们用一个set来记录当前的个数，hashmap来记录这个值到底出现了几回，以便我们在向右移动窗口的时候set中的值是否需要变化。

代码如下

import java.util.*;

public class maogan {
    public static void main(String[] args) {
        List talent=new ArrayList();
        talent.add(1);
        talent.add(1);
        talent.add(2);
        talent.add(2);
        talent.add(3);
        talent.add(1);
        talent.add(3);
        talent.add(2);
        maogan maogan=new maogan();
        maogan.teamSize(talent,3);
    }
    public List teamSize(List talent, int talentsCount) {
        // 本道题的思路为滑动窗口
        Set set=new HashSet();//用set来判断是否有n个数
        Map map=new HashMap();//用来存放当前的数的个数
        int length=talent.size();
        List list=new ArrayList(length);
        int index=0;//当前边界
        for(int i=0;i 
少壮不努力，老大徒伤悲！继续加油吧～