class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int [] a = new int[len];
        for(int i = len;i > 0;i--){
            for(int j = 1;j <= len+1-i;j++){
                String str = s.substring(j-1,j-1+i); // 获取截取字符串
                HashSet set = new HashSet();
                for(int k = 0;k < i;k++){
                    set.add(str.charAt(k)); // 遍历存入set中
                    if(set.size() != k+1){
                        break;
                    }else if(set.size() == i){
                        return i;
                    }
                }
            }
        }
        return 0;
    }
}

class Solution {
   public List<Integer> findSubstring(String s, String[] words) {
        ArrayList<Integer> res = new ArrayList();
        int strslen =  words.length * words[0].length();  //串联子串的长度
        if(s.length() < strslen){
            return res;
        }
        int slen = s.length();
        int wlen = words.length;
        int len = words[0].length();
        HashMap<String,Integer> map = new HashMap();
        //存放所有words，key对应words里的子串，value对应个数
        for(int i = 0;i < wlen;i++){
            if(map.containsKey(words[i])){
                map.put(words[i],map.get(words[i])+1);
            }else {
                map.put(words[i],1);
            }
        }
        for(int i = 0;i < slen;i++){
            //长度太短，直接返回
            if(slen - i < strslen){
                return res;
            }
            //与words[i]等长的字符串
            String temp;
            if(!map.containsKey(s.substring(i,i+len))){
                continue;
            }
            //复制一个map
            HashMap<String,Integer> clone = (HashMap<String, Integer>) map.clone();
            int index = i;
            while(index - i < strslen){
                temp = s.substring(index,index+len);
                //不包含，或者words里对应的的子串用完
                if(!clone.containsKey(temp) || clone.containsKey(temp) && clone.get(temp) == 0){
                    break;
                }else {
                    //value-1
                    clone.put(temp,clone.get(temp)-1);
                    index += len;
                }
            }
            if(index == i + strslen){
                res.add(i);
            }
        }
        return res;
    }
}

class Solution {
    public String minWindow(String s, String t) {
		int len = t.length();
		if (len > s.length())
			return "";
		int[] origin = new int[128];
		for (int i = 0; i < len; i++) {
			origin[t.charAt(i)]++;
		}

		for (int space = len - 1; space < s.length(); space++) {
			int[] compare = null;
			int left, right;
			for (left = 0, right = left + space; right < s.length(); left++, right++) {
				if (compare == null) {
					compare = new int[128];
					for (int i = 0; i <= right; i++) {
						compare[s.charAt(i)]++;
					}
					int i = 0;
					for (; i < t.length(); i++) {
						if (compare[t.charAt(i)] < origin[t.charAt(i)])
							break;
					}
					if (i == t.length())
						return s.substring(left, right+1);
				} else {
					compare[s.charAt(left - 1)]--;
					compare[s.charAt(right)]++;
					int i = 0;
					for (; i < t.length(); i++) {
						if (compare[t.charAt(i)] < origin[t.charAt(i)])
							break;
					}
					if (i == t.length())
						return s.substring(left, right+1);
				}
			}
		}
		return "";
	}
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int len = nums.length;
        int left = 0, right = 0;
        int sum = 0;
        while (right < len) {
            sum += nums[right++];
            while (sum >= target) {
                res = Math.min(res, right - left);
                sum -= nums[left++];
            }
        }
        
        return (res == Integer.MAX_VALUE) ? 0 : res;
    }
}

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0,max = 0;
        if (nums.length <= k) {
            for (int num : nums) {
                sum += num;
            }
            return (double) sum / k;
        }
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        max = sum;
        for (int i = k; i < nums.length; i++) {
            max = Math.max(max,sum = sum - nums[i-k] + nums[i]);

        }
        return (double) max / k;
    }
}