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

LeetCode热题100(子串篇)

article 2025/1/20 22:58:10

LeetCode热题100
说是子串，其实是子区间~

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。
子数组是数组中元素的连续非空序列。
在这里插入图片描述

思路

思路：
和为k的子数组，看到子数组的和，首先想到的就是滑动窗口或者前缀和，但是因为这里的数据有负数，不满足滑动窗口的单调性，那么我们来看前缀和。
前缀和：p[i] = p[i-1]+nums[i] (i>0，p[0] = nums[0])
有了前缀和，我们可以求到所有的子数组的和。
比如：我们要求l到r区间的和
可以使用p[r]-p[l-1]求得。
了解这个原理后，我们在来看题目要求：和为k的数组的数目。
也就是p[r]-p[l-1] = k
p[l-1] = p[r] - k
替换l-1为i，r为j，（i<j）
p[i] = p[j] - k
得到这个式子，你有想法了吗
p[i]是p[j]前面的前缀和，那么我们可以使用一个哈希表来存储p[i],val为p[i]的数目，因为p[j]是之后的前缀和，所有我们可以去哈希表中去找有有没有满足p[j]-k的之前的前缀和。

代码

C++

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        int count = 0,p = 0;
        cnt[0] = 1;
        for(int i = 0;i<nums.size();++i){
            p+=nums[i];
            count+=(cnt.contains(p-k))?cnt[p-k]:0;
            cnt[p]++;
        }
        return count;
    }
};

Java

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> cnt = new HashMap<>();
        int ans = 0,prev = 0;
        cnt.merge(0,1,Integer::sum);
        for(int num:nums){
            prev+=num;
            if(cnt.containsKey(prev-k)){
                ans+=cnt.get(prev-k);
            }
            cnt.merge(prev,1,Integer::sum);
        }
        return ans;
    }
}

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans,prev = 0,0
        cnt= {0:1}
        for num in nums:
            prev+=num
            if prev-k in cnt:
                ans+=cnt[prev-k]
            cnt[prev] = cnt.get(prev,0)+1
        return ans

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
在这里插入图片描述

思路

思路：滑动窗口最大值
求一个动态的最大值，你会想到什么数据结构，优先队列就是很匹配的数据结构，大根堆的堆顶永远都是最大值。
选定了数据结构，我们开始分析这题适用不适用。
将区间内的数，存储到优先队列中，此时堆顶的值就是最大值，开始移动区间。在填入新元素后，我们就要开始判断堆顶的数据是否在新的区间内，如果不在新区间内，那么就可以把这个数从堆中移除了，这个值永远不可能出现在滑动窗口中了。
不断地移除堆顶元素，直到堆顶元素确实出现在滑动窗口中，此时堆顶元素就是滑动窗口地最大值。
为了方便判断堆顶元素于滑动窗口的位置关系，我们可以在优先队列中存储二元组，表示元素num在数组中的下标index。

代码

C++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>> q;
        vector<int> ans;
        int n = nums.size();
        for(int i = 0;i<k;++i){
            q.emplace(nums[i],i);
        }
        ans.push_back(q.top().first);
        for(int i = k;i<n;++i){
            q.emplace(nums[i],i);
            while(q.top().second<=i-k){
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
        ArrayList<Integer> ans = new ArrayList<>();
        int n = nums.length;
        for(int l = 0,r = 0;r<n;++r){
            heap.add(new java.util.AbstractMap.SimpleEntry<>(nums[r], r));
            while(r-l+1>=k){
                if(r-l+1 == k){
                    while(r-heap.peek().getValue()+1>k) heap.poll();
                    ans.add(heap.peek().getKey());
                }
                l++;
            }
        }
        int[] ret = ans.stream().mapToInt(Integer::intValue).toArray();
        return ret;
    }
}

Python

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        heap = []
        ans = []
        l,r = 0,0
        while r<len(nums):
            heapq.heappush(heap,(-nums[r],r))
            while r-l+1>=k:
                if(r-l+1==k):
                    while r-heap[0][1]+1>k:
                        heapq.heappop(heap)
                    ans.append(-heap[0][0])
                l+=1
            r+=1
        return ans

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
在这里插入图片描述

思路

思路：最小覆盖子串
使用两个哈希表，分别命名为cnt1和cnt2。cnt1存储的t串的字符及其对应的数字。
定义一个valid表示满足要求的字符数目。
开始滑动窗口，一旦字串是cnt1中的字符，我们就让cnt2存储这个字符，如果此时满足cnt2中存储的该字符数目与cnt1中的该字符相等，就让valid数目加加，后面都是经典的滑动窗口内容了。

代码

C++

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> cnt1,cnt2;
        for(char&c:t){
            cnt1[c]++;
        }
        int strLen = INT_MAX,valid=0;
        int begin = 0;
        for(int l = 0,r = 0;r<s.size();++r){
            if(cnt1.count(s[r])){
                cnt2[s[r]]++;
                if(cnt1[s[r]] == cnt2[s[r]]){
                    valid++;
                }
            }
            while(valid == cnt1.size()){
                char c = s[l];
                if(strLen>r-l+1){
                    strLen = r-l+1;
                    begin = l;
                }
                if(cnt1.count(c)){
                    if(cnt1[c] == cnt2[c]){
                        valid--;
                    }
                    cnt2[c]--;
                }

                l++;
            }
        }
        return strLen==INT_MAX?"":s.substr(begin,strLen);
    }
};

Python

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n,m = len(s),len(t)
        cnt = {}
        for c in t:
            cnt[c] = cnt.get(c,0)+1
        subLen = 0x3f3f3f3f
        mp = {}
        p = ()
        l,r,valid = 0,0,0
        while r<n:
            c = s[r]
            if c in cnt:
                mp[c] = mp.get(c,0)+1
                if mp[c] == cnt[c]:
                    valid+=1
            while valid == len(cnt):
                c = s[l]
                if(subLen>r-l+1):
                    subLen = r-l+1
                    p = (l,subLen)
                if c in cnt:
                    if mp[c] == cnt[c]:
                        valid-=1
                    mp[c] -= 1
                l+=1
            r+=1
        if subLen == 0x3f3f3f3f:
            return ""
        return s[p[0]:p[0]+p[1]]