Day10--滑动窗口与双指针--2875. 无限数组的最短子数组，76. 最小覆盖子串，632. 最小区间

思路【我】：

• 三步曲：入–更新–出。
• 关键是结束循环的判断：
  • 情况一：如果i和left都在第二层了，minLen无值，返回-1，有值，返回minLen
  • 情况二：如果i在第二层，left在第一层，证明还在累加中，继续

class Solution {public int minSizeSubarray(int[] nums, int target) {int n = nums.length;int sum = 0;int minLen = Integer.MAX_VALUE;int left = 0;for (int i = 0;; i++) {// 1，入sum += nums[i % n];// 2，出while (sum > target) {sum -= nums[left % n];left++;}// 3，更新if (sum == target) {minLen = Math.min(minLen, i - left + 1);}// 4，判断是否可以结束循环：// 情况一：如果i和left都在第二层了，minLen无值，返回-1，有值，返回minLen// 情况二：如果i在第二层，left在第一层，证明还在累加中，继续if (i > n && left > n) {if (minLen == Integer.MAX_VALUE) {return -1;} else {return minLen;}}if (i > n && left < n) {continue;}}}
}

思路【灵艾山茶府】：

有点烧脑，直接看图吧。很难用纯文字描述出来。(图片来自@灵艾山茶府）

class Solution {public int minSizeSubarray(int[] nums, int target) {int n = nums.length;int total = Arrays.stream(nums).sum();int minLen = Integer.MAX_VALUE;int left = 0;int sum = 0;int rem = target % total;for (int i = 0; i < n * 2; i++) {sum += nums[i % n];while (sum > rem) {sum -= nums[left % n];left++;}if (sum == rem) {minLen = Math.min(minLen, i - left + 1);}}return minLen == Integer.MAX_VALUE ? -1 : minLen + (int) (target / total) * n;}
}

思路【我】：

1. 使用mapS和mapT，分别记录窗口中的字母，和t串中的字符
2. 三步曲：入–更新–出
   1. 入。
   2. 当覆盖的时候，更新minLen，记录起始索引index
   3. 出。

class Solution {public String minWindow(String s, String t) {char[] ss = s.toCharArray();char[] tt = t.toCharArray();int[] mapS = new int[128];int[] mapT = new int[128];for (int i = 0; i < tt.length; i++) {mapT[tt[i]]++;}int left = 0;int minLen = Integer.MAX_VALUE;// 答案串的起始索引int index = -1;for (int i = 0; i < ss.length; i++) {// 1，入mapS[ss[i]]++;// 当覆盖的时候while (isCover(mapS, mapT)) {// 2,更新// 这里不能用minLen = Math.min()的写法// 因为index需要minLen的更新状态来判断要不要更新int len = i - left + 1;if (len < minLen) {minLen = len;index = left;}// 3,出mapS[ss[left]]--;left++;}}return minLen == Integer.MAX_VALUE ? "" : new String(ss, index, minLen);}// 窗口是否cover了tprivate boolean isCover(int[] mapS, int[] mapT) {// 这里可以直接写成for(i=0;i<128)整个数组比较完，因为其他位置是0，也不影响。但是语义不清晰了for (int i = 'a'; i <= 'z'; i++) {if (mapT[i] > mapS[i]) {return false;}}for (int i = 'A'; i <= 'Z'; i++) {if (mapT[i] > mapS[i]) {return false;}}return true;}
}

思路【灵艾山茶府】：

1. 利用多一个参数type来记录t串中的字母的种类数。
2. mapT初始值是t串中各字母出现的次数，在滑动窗口的时候，可以理解为，s需要全覆盖t，还需要把哪个数值减为零。
3. 三步曲：入–更新–出
   1. 入。mapT[ss[i]]--;。关注mapT[ss[i]]==0的情况，正值减到0了，证明有一种字母已经满足了，因此type–
   2. 当种类为0了，证明全覆盖，可以更新minLen了。
   3. 出。“入”的操作取反，就是把对应减掉的数值加回去mapT[ss[left]]++;。关注mapT[ss[left]]==1，当该数值首次为1的时候，证明不匹配的字母又多了一种，因此type++。

class Solution {public String minWindow(String s, String t) {char[] ss = s.toCharArray();char[] tt = t.toCharArray();// 记录t串种字母的种类数type，和各字母的出现次数int[] mapT = new int[128];int type = 0;for (int i = 0; i < tt.length; i++) {mapT[tt[i]]++;if(mapT[tt[i]]==1){type++;}}int index = -1;int left = 0;int minLen = Integer.MAX_VALUE;// 滑动窗口（遍历s）for (int i = 0; i < ss.length; i++) {// 1，入// （如果t没有对应的字母的话，会变成负值，这部分不用管，s本来就比t大）mapT[ss[i]]--;// 重点关注，现在是已经减一了，还等于0的话，证明原来是正值// 正值减到0了，证明有一种字母已经满足了，因此type--if(mapT[ss[i]]==0){type--;}// 当种类为0了，证明全覆盖while (type==0) {// 2,更新int len = i - left + 1;if (len < minLen) {minLen = len;index = left;}// 3,出// “入”的操作取反，就是把对应减掉的数值加回去mapT[ss[left]]++;// 当该数值首次为1的时候，证明不匹配的字母又多了一种，因此type++if(mapT[ss[left]]==1){type++;}left++;}}return minLen == Integer.MAX_VALUE ? "" : new String(ss, index, minLen);}
}

方法：滑动窗口

思路【灵艾山茶府】：

1. 把所有列表都合成一个列表，然后记录这个元素是哪个列表来的。
   • 新建Pair类，有val和listID变量
   • 根据val，对pairs进行排序
2. 利用数组countInList[listID]，记录那个列表有多少个元素进入窗口
3. 三步曲：入–更新–出
   1. 入。右指针入窗，当countInList[rightList]==1时，进入窗口的types++
   2. 更新。当types==k个列表的时候，可以更新。
      • 注意！这次不是更新索引，而是rightVal和leftVal
   3. 出。左指针出窗，当countInList[leftList] == 0时，进入窗口的types–

class Solution {public int[] smallestRange(List<List<Integer>> nums) {int n = 0;for (List<Integer> list : nums) {n += list.size();}Pair[] pairs = new Pair[n];int p = 0;for (int i = 0; i < nums.size(); i++) {for (int x : nums.get(i)) {pairs[p++] = new Pair(x, i);}}Arrays.sort(pairs, (o1, o2) -> Integer.compare(o1.val, o2.val));int left = 0;int ansL = pairs[0].val;int ansR = pairs[n - 1].val;int types = 0;int[] countInList = new int[nums.size()];for (int i = 0; i < n; i++) {int rightVal = pairs[i].val;int rightList = pairs[i].listID;countInList[rightList]++;if (countInList[rightList] == 1) {types++;}while (types == nums.size()) {int leftVal = pairs[left].val;int leftList = pairs[left].listID;if (rightVal - leftVal < ansR - ansL) {ansR = rightVal;ansL = leftVal;}countInList[leftList]--;if (countInList[leftList] == 0) {types--;}left++;}}return new int[] { ansL, ansR };}class Pair {int val;int listID;public Pair(int val, int listID) {this.val = val;this.listID = listID;}}
}

方法：堆排序，优先队列

思路【灵艾山茶府】：

注：堆排序相当于枚举合法区间的左端点，而滑动窗口相当于枚举合法区间的右端点。

暂时先不写，学到堆再做。