算法题（子串）

一、题目

1、滑动窗口最大值（LC 239）

2、最小覆盖子串（LC 76）

二、题解

1、滑动窗口最大值（LC 239）

（1）分析

方法一：暴力。两层for循环，内循环求每个窗口的最大元素，外循环遍历每个窗口，将每次的最大元素存放在数组中，最后输出这个数组。时间复杂度较高，大量数据会导致超时。

方法二：使用双端队列的方法解决。假设滑动窗口的左右两端为 i 和 j ，先放nums[0]到双端队列队列，此后每添加一个新的元素nums[j]到队列前，把之前队列中的小于nums[j] 的元素都移出队列，也需要把不在这个窗口的元素移出队列。这样可以保证，每移动一次窗口，双端队列的首元素就是该窗口最大的元素，直接添加首元素到最终返回的数组中。

（2）解答

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums==null||k==0){return new int[0];} int[] res = new int[nums.length-k+1]; Deque<Integer> deque = new LinkedList<>(); for(int j=0, i=1-k; j<nums.length; i++, j++){ if(i>0&&deque.peekFirst()==nums[i-1]){ deque.removeFirst(); } while(!deque.isEmpty()&&deque.peekLast()<nums[j]){ deque.removeLast(); } deque.addLast(nums[j]); if(i>=0){ res[i] = deque.peekFirst(); } } return res; } }

2、最小覆盖子串（LC 76）

（1）分析

创建两个数组统计给定的两个字符串字符出现的频次，以字符的ASCII值为下标，数组元素的大小表示字符出现的频次。设立左右指针，初始都为0，右指针先往右移动，并统计出现t字符串中字符的频次存储在数组中，当新数组包含t的数组，即每次字符出现的频次都大于t时，左指针向右移动，每移动一次减少一个字符频次，直至新数组不再包含t的数组，继续移动右指针，重复上述过程到遍历到最后一个字符。过程中不断更新左右指针差值最短的情况。取 resRight-resLef 最小的时候，分割该段字符串，就是所求的最短窗口子串。

（2）解答

class Solution { public String minWindow(String s, String t) { int[] arrS = new int[128]; int[] arrT = new int[128]; for(char c : t.toCharArray()){ arrT[c]++; } char[] chS = s.toCharArray(); int resLeft = -1; int resRight = chS.length; int left = 0; int right = 0; for(right=0; right<chS.length; right++){ arrS[chS[right]]++; while(isCovered(arrS,arrT)){ if(resRight-resLeft>right-left){ resLeft = left; resRight = right; } arrS[chS[left]]--; left++; } } return resLeft>-1? s.substring(resLeft,resRight+1): ""; } public boolean isCovered(int[] arrS, int[] arrT){ for(int i='a'; i<='z'; i++){ if(arrS[i]<arrT[i]){ return false; } } for(int i='A'; i<='Z'; i++){ if(arrS[i]<arrT[i]){ return false; } } return true; } }