当前位置：首页 > article >正文

LeetCode Hot100 - 子串篇

article 2024/10/31 18:28:20

前言

挑战一个月刷完力扣的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的和为k
            if(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;
    }
}