算法题（子串）

一、题目1、滑动窗口最大值LC 2392、最小覆盖子串LC 76二、题解1、滑动窗口最大值LC 2391分析方法一暴力。两层for循环内循环求每个窗口的最大元素外循环遍历每个窗口将每次的最大元素存放在数组中最后输出这个数组。时间复杂度较高大量数据会导致超时。方法二使用双端队列的方法解决。假设滑动窗口的左右两端为 i 和 j 先放nums[0]到双端队列队列此后每添加一个新的元素nums[j]到队列前把之前队列中的小于nums[j] 的元素都移出队列也需要把不在这个窗口的元素移出队列。这样可以保证每移动一次窗口双端队列的首元素就是该窗口最大的元素直接添加首元素到最终返回的数组中。2解答class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(numsnull||k0){return new int[0];} int[] res new int[nums.length-k1]; DequeInteger deque new LinkedList(); for(int j0, i1-k; jnums.length; i, j){ if(i0deque.peekFirst()nums[i-1]){ deque.removeFirst(); } while(!deque.isEmpty()deque.peekLast()nums[j]){ deque.removeLast(); } deque.addLast(nums[j]); if(i0){ res[i] deque.peekFirst(); } } return res; } }2、最小覆盖子串LC 761分析创建两个数组统计给定的两个字符串字符出现的频次以字符的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(right0; rightchS.length; right){ arrS[chS[right]]; while(isCovered(arrS,arrT)){ if(resRight-resLeftright-left){ resLeft left; resRight right; } arrS[chS[left]]--; left; } } return resLeft-1? s.substring(resLeft,resRight1): ; } public boolean isCovered(int[] arrS, int[] arrT){ for(int ia; iz; i){ if(arrS[i]arrT[i]){ return false; } } for(int iA; iZ; i){ if(arrS[i]arrT[i]){ return false; } } return true; } }