LeetCode Hot100 - 子串篇

前言

        挑战一个月刷完力扣的hot100，记录一下每题的思路~

        这次是子串相关的题目

（1）560. 和为 K 的子数组

        ①暴力枚举，使用一个变量sum记录以l开头r结尾的情况

class Solution {public int subarraySum(int[] nums, int k) {int res=0;// 枚举每种情况for(int l=0;l<nums.length;l++){int sum=0; // l开头for(int r=l;r<nums.length;r++){ // r结尾sum+=nums[r];if(sum==k)res++; // 满足条件}}return res;}
}

        ②前缀和+map，map记录每种前缀和出现的次数。若位置i的前缀和为pre，map中存在pre-k的前缀和，即存在某位置到i的和为k，统计次数即可

class Solution {Map<Integer,Integer> map = new HashMap<>(); // 每种前缀和出现次数public int subarraySum(int[] nums, int k) {int res=0, pre=0;map.put(0,1);for(int i=0;i<nums.length;i++){pre+=nums[i]; // 开头到i的和// map中存在前缀和pre-k，即存在某个位置到i的和为kif(map.containsKey(pre-k))res+=map.get(pre-k);map.put(pre,map.getOrDefault(pre,0)+1); // 更新前缀和pre的次数}return res;}
}

（2）239. 滑动窗口最大值

        ①优先队列，记录值和下标，按值降序（越大越优先），每次移除下标越界元素，取最大值

class Solution {// 优先队列，存值和下标，按值降序，即越大优先级越高PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->Integer.compare(b[0],a[0]));List<Integer> res = new ArrayList<>();public int[] maxSlidingWindow(int[] nums, int k) {for(int i=0;i<k;i++)pq.offer(new int[]{nums[i],i});res.add(pq.peek()[0]); // 第一种情况for(int i=k;i<nums.length;i++){pq.offer(new int[]{nums[i],i});while(pq.peek()[1]<=i-k)pq.poll(); // 移除窗口外元素res.add(pq.peek()[0]); // 存最大值}return res.stream().mapToInt(Integer::intValue).toArray(); // 流式转换}
}

        ②单调递减双端队列。若l<r，且nums[l]<nums[r]，在后续的窗口中不可能选到l。每次入队为靠后元素，若该元素大于队尾元素，队尾不可能再选到，直接出队。队列保留目前最大值和其后递减较小值。最大值移出滑动窗口时，将其出队

class Solution {List<Integer> res = new ArrayList<>();Deque<Integer> queue = new ArrayDeque<>(); // 单调递减双端队列public int[] maxSlidingWindow(int[] nums, int k) {for(int i=0;i<nums.length;i++){// 移除窗口的元素刚好为队头，出队if(i>=k&&queue.peekFirst()==nums[i-k])queue.pollFirst();// 加入当前元素，满足单调递减while(!queue.isEmpty()&&queue.peekLast()<nums[i])queue.pollLast();queue.addLast(nums[i]);// 遍历到k-1时开始取队头，即目前最大值if(i>=k-1)res.add(queue.peekFirst());}return res.stream().mapToInt(Integer::intValue).toArray();}
}

        ③思路同上一种，单调队列记录下标，用于队头下标越界判断，更好理解

class Solution {List<Integer> res = new ArrayList<>();Deque<Integer> deque = new ArrayDeque<>(); // 单调递减双端队列public int[] maxSlidingWindow(int[] nums, int k) {for(int i=0;i<nums.length;i++){// 加入当前元素，满足单调递减while(!deque.isEmpty()&&nums[deque.peekLast()]<nums[i])deque.pollLast();deque.addLast(i);// 队头出界，移出if(i>=k&&deque.peekFirst()<=i-k)deque.pollFirst();// 遍历到k-1时开始取队头，即目前最大值if(i>=k-1)res.add(nums[deque.peekFirst()]);}return res.stream().mapToInt(Integer::intValue).toArray();}
}

        ④分组+最大前后缀。k个数一组，计算每组最大前后缀。窗口起始值i，若为k的整数倍，即窗口恰好为一组；否则，窗口跨越两个分组，取前一个分组最大后缀和后一个分组最大前缀的最大值

class Solution {List<Integer> res = new ArrayList<>();public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int[] prefixMax=new int[n], suffixMax=new int[n];for(int i=0,j=n-1;i<n;i++,j--){// 下标为k整数倍，组头if(i%k==0)prefixMax[i]=nums[i]; else prefixMax[i]=Math.max(prefixMax[i-1],nums[i]);// 数组最后一位或下标后一位为k整数倍，组尾if(j==n-1||(j+1)%k==0)suffixMax[j]=nums[j]; else suffixMax[j]=Math.max(suffixMax[j+1],nums[j]);}// i为窗口起始位置// i为k整数倍，窗口恰为一个分组// 否则窗口跨越两个分组，取前一个分组最大后缀和后一个分组最大前缀的最大值for(int i=0;i<=n-k;i++)res.add(Math.max(suffixMax[i],prefixMax[i+k-1]));return res.stream().mapToInt(Integer::intValue).toArray();}
}

（3）76. 最小覆盖子串

        滑动窗口。map和count分别记录t和滑动窗口的字符数，check判断count不小于map，即滑动窗口满足条件。r扩张直到check为true，然后收缩l直到不满足，记录最短滑动窗口

class Solution {Map<Character,Integer> map = new HashMap<>();Map<Character,Integer> count = new HashMap<>();public String minWindow(String s, String t) {if(s.length()<t.length())return ""; // 长度不够int l=0,r=-1,sLen=s.length(),tLen=t.length(); // 滑动窗口int resL=-1,resR=-1; // 结果下标// t中字符计数for(char c:t.toCharArray())map.put(c,map.getOrDefault(c,0)+1);// s滑动窗口while(r<sLen){r++; // 扩张if(r<sLen&&map.containsKey(s.charAt(r)))count.put(s.charAt(r),count.getOrDefault(s.charAt(r),0)+1);while(check()&&l<=r){if(resL==-1||r-l<resR-resL){resL=l;resR=r;}if(map.containsKey(s.charAt(l)))count.put(s.charAt(l),count.getOrDefault(s.charAt(l),0)-1);l++; // 收缩}}return resL==-1?"":s.substring(resL,resR+1);}// count不小于map个数boolean check(){for(Character c:map.keySet()){if(count.getOrDefault(c,0)<map.get(c))return false;}return true;}
}

总结

        ①子串。双指针暴力枚举；map记录每种前缀和出现次数，统计pre-k存在次数

        ②和为K的子串。优先队列记录值和下标，值大优先，下标限界；单调递减双端队列，位于前面且更小的值不会再被选中；分组+最大前后缀，预处理分组的前后缀，滑动窗口恰为分组，或跨越两个分组

        ③滑动窗口最大值。滑动窗口，r扩张找到满足的情况，l收缩尽可能最短