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

LeetCode热题100(子串篇)

news 来源：原创 2025/6/8 20:57:38

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,0cnt= {0:1}for num in nums:prev+=numif prev-k in cnt:ans+=cnt[prev-k]cnt[prev] = cnt.get(prev,0)+1return 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,0while 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+=1r+=1return 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)+1subLen = 0x3f3f3f3fmp = {}p = ()l,r,valid = 0,0,0while r<n:c = s[r]if c in cnt:mp[c] = mp.get(c,0)+1if mp[c] == cnt[c]:valid+=1while valid == len(cnt):c = s[l]if(subLen>r-l+1):subLen = r-l+1p = (l,subLen)if c in cnt:if mp[c] == cnt[c]:valid-=1mp[c] -= 1l+=1r+=1if subLen == 0x3f3f3f3f:return ""return s[p[0]:p[0]+p[1]]

总结

子区间在算法题中是非常常见的问题，遇到这种题你应该想到的算法有动态规划，滑动窗口，前缀和等等。
本系列记录我的刷题历程。

560. 和为 K 的子数组

思路

代码

C++

Java

Python

239. 滑动窗口最大值

思路

代码

C++

Java

Python

76. 最小覆盖子串

思路

代码

C++

Python

总结

相关文章：