算法总结（七） 滑动窗口

累加和大于等于k的最小长度子数组

都是正数，所以滑动窗口具有单调性，加入新数肯定会导致累加和变大，减少数字会导致累加和变小。

   public static int minSubArrayLen(int target, int[] nums) {
	int ans = Integer.MAX_VALUE;
	for (int l = 0, r = 0, sum = 0; r < nums.length; r++) {
		sum += nums[r];
		while (sum - nums[l] >= target) {
			// sum : nums[l....r]
			// 如果l位置的数从窗口出去，还能继续达标，那就出去
			sum -= nums[l++];
		}
		if (sum >= target) {
			ans = Math.min(ans, r - l + 1);
		}
	}
	return ans == Integer.MAX_VALUE ? 0 : ans;
}

无重复子串的最长长度

记录上次这个字符出现的位置，每次更新左边界，就用当前左边界跟（上次重复位置+1）的最大值即可。

   public static int lengthOfLongestSubstring(String str) {
	char[] s = str.toCharArray();
	int n = s.length;
	// char -> int -> 0 ~ 255
	// 每一种字符上次出现的位置
	int[] last = new int[256];
	// 所有字符都没有上次出现的位置
	Arrays.fill(last, -1);
	// 不含有重复字符的 最长子串 的长度
	int ans = 0;
	for (int l = 0, r = 0; r < n; r++) {
		l = Math.max(l, last[s[r]] + 1);
		ans = Math.max(ans, r - l + 1);
		// 更新当前字符上一次出现的位置
		last[s[r]] = r;
	}
	return ans;
}

最小覆盖子串

描述：给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 “”。

等到满足覆盖条件之后，再开始考虑移动左边界。，只有移动左边界不会导致覆盖条件失效，才能移动。

   public static String minWindow(String str, String tar) {
	char[] s = str.toCharArray();
	char[] t = tar.toCharArray();
	// 每种字符的欠债情况
	// cnts[i] = 负数，代表字符i有负债
	// cnts[i] = 正数，代表字符i有盈余
	int[] cnts = new int[256];
	for (char cha : t) {
		cnts[cha]--;
	}
	// 最小覆盖子串的长度
	int len = Integer.MAX_VALUE;
	// 从哪个位置开头，发现的最小覆盖子串
	int start = 0;
	// 总债务
	int debt = t.length;
	for (int l = 0, r = 0; r < s.length; r++) {
		// 窗口右边界向右，给出字符
		if (cnts[s[r]]++ < 0) {
			debt--;
		}
		if (debt == 0) {
			// 窗口左边界向右，拿回字符
			while (cnts[s[l]] > 0) {
				cnts[s[l++]]--;
			}
			// 以r位置结尾的达标窗口，更新答案
			if (r - l + 1 < len) {
				len = r - l + 1;
				start = l;
			}
		}
	}
	return len == Integer.MAX_VALUE ? "" : str.substring(start, start + len);
}

替换子串得到平衡字符串

解释：有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

思路：跟最小覆盖子串思路一样。只需要找到哪些字符超过了多少，我们替换他即可。

public int balancedString(String s) {
    int[] cnt = new int[4];
    int n = s.length();
    for(int i=0;i<s.length();i++){
        char c = s.charAt(i);
        int pos = c == 'W' ? 1 : (c == 'E' ? 2 : (c== 'R' ? 3 : 0));
        cnt[pos]++;
    }
    int debat = 0 ;
    for(int i =0;i<4;i++){
        if(cnt[i] <= n/4){
            cnt[i] = 0;
        }else {
            cnt[i] = n/4 - cnt[i];
            debat-=cnt[i];
        }
    }
    if(debat == 0){
        return 0;
    }

    int ans = Integer.MAX_VALUE;

    for(int r=0,l=0;r<s.length();r++){
        char c = s.charAt(r);
        int pos = c == 'W' ? 1 : (c == 'E' ? 2 : (c== 'R' ? 3 : 0));
        if(cnt[pos]++ < 0){
            debat--;
        }
        if(debat == 0){
            c = s.charAt(l);
            pos = c == 'W' ? 1 : (c == 'E' ? 2 : (c== 'R' ? 3 : 0));
            while( cnt[pos] > 0){
                cnt[pos]--;
                l++;
                c = s.charAt(l);
                pos = c == 'W' ? 1 : (c == 'E' ? 2 : (c== 'R' ? 3 : 0));
            }
            ans = Math.min(ans,r-l+1);
        }
    }
    return ans;
}

K个不同整数的子数组

描述：给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。

例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
子数组 是数组的 连续 部分。

思路：转化为求不超过k个不同整数问题，用k 减去 k-1 对应的答案 就是刚好个数为k的个数。

对于不超过这个问题用滑动窗口解决，只要种类不超过就扩大窗口，否则缩小窗口直到种类不超过。然后统计以窗口右边结尾的子数组的个数。即r-l+1.每次累加这个结果即可。

public int subarraysWithKDistinct(int[] nums, int k) {
    // 不超过k个不同整数
    return find(nums,k) - find(nums,k-1);
}
public static final int MAX = 20001;

public static int[] cnt = new int[MAX];

public int find(int[] nums,int k){
    Arrays.fill(cnt,0);
    int sum = 0;
    int kinds = 0;
    for(int l=0,r=0;r<nums.length;r++){
        // 窗口右边界向右，给出字符,并判断是不是新的
        if(++cnt[nums[r]] == 1){
            kinds++;
        }
        while (kinds > k){
            // 窗口左边界向右，拿回字符，如果一个字符没有了，则种类减一
            if( -- cnt[nums[l++]] == 0){
                kinds--;
            }
        }
        // 以r位置结尾的达标窗口，累加个数
        sum+= r-l+1;
    }
    return sum;
}