Hot100之子串
560和为K的子数组
题目
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列
思路解析
ps：我们的presum【0】就是0，如果没有这个0的话我们的第一个元素就无法减去上一个元素，为了让我们的第一个元素也能参与前缀和减法，所以我们的presum【0】就是0
我们首先收集前缀和
然后我们两个for循环，里面前缀和作差
然后count++收集答案
代码
class Solution {
public int subarraySum(int[] nums, int k) {
//前缀和数组
int[] presum = new int[nums.length+1];
for (int i = 0; i < nums.length; i++) {
//这里需要注意，我们的前缀和是presum[1]开始填充的
presum[i+1] = nums[i] + presum[i];
}
//统计个数
int count = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = i; j < nums.length; ++j) {
//注意偏移，因为我们的nums[2]到nums[4]等于presum[5]-presum[2]
//所以这样就可以得到nums[i,j]区间内的和
if (presum[j+1] - presum[i] == k) {
count++;
}
}
}
return count;
}
}
239滑动窗口的最大值
题目
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位
思路解析
简单的单调栈+滑动窗口思想
我们维护栈内单调递减就行
当里面元素个数大于K的时候，我们就弹出第一个元素就好了
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new ArrayDeque<>();
int n = nums.length;
// 初始化收集结果的数组
int result[] = new int[n - k + 1];
for (int i = 0; i < n; i++) {
// 入
while (!deque.isEmpty() && nums[deque.getLast()] <= nums[i]) {
deque.removeLast(); // 维护q的单调性
}
deque.addLast(i); // 入队,这是把我们的下标给存进去
if (i - deque.getFirst() >= k) {
// 这个是我们的队首已经离开窗口了
deque.removeFirst();
}
// 收集我们的答案
if (i >= k - 1) {
result[i - k + 1] = nums[deque.getFirst()];
}
}
return result;
}
}前置知识--209长度最小的子数组
题目
思路解析
不断缩小左端点
代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0, n = nums.length;
int min = Integer.MAX_VALUE;
int sum = 0;
while (right < n) {
sum += nums[right];
while (sum >= target) {
min = Math.min(min, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}76最小覆盖子串
题目
去看上一节的前置知识先
思路解析
字符数组的含义
我们把子串变成字符数组，父串变成字符数组
数组的逻辑是，我们遍历字符串，对特定的字符进行计数，也就是++
char[] SChar = s.toCharArray();//子串的数组
int m=s.length();//子串的长度
int ansLeft=-1;
int ansRight=m;
int[] cntS=new int[128];//s子串的字母出现次数,s是子串
int[] cntT=new int[128];//t字符串中字母出现的次数,t是父串
//对父串中的字符的值进行初始化
for(char c:t.toCharArray()){
cntT[c]++;
}涵盖函数
然后我们弄个涵盖函数，判断当前字符串是否涵盖
如果父串里面的字符比子串多,我们返回false,说明这个子串没有涵盖父串的所有字符
如果子串里的字符数量都比子串多,那么说明这个子串没问题,这个子串涵盖了父串中的所有字符
//如果父串里面的字符比子串多,我们返回false,说明这个子串并没有涵盖父串的所有字符
//如果子串里的字符数量都比子串多,那么说明这个子串没问题,这个子串涵盖了父串中的所有字符
private boolean isCovered(int[] cntS,int[] cntT)
{
for(int i='A';i<='Z';i++){
if(cntS[i]<cntT[i]){
return false;
}
}
for(int i='a';i<='z';i++){
if(cntS[i]<cntT[i]){
return false;
}
}
return true;
}滑动窗口思想
我们遍历子串，操作子串
子串进入数组，然后根据我们的涵盖函数
如果涵盖+找到了更短的子串，那我们就计算最短长度然后记住left和right
然后弹出最左侧元素，也就是left++进行我们的滑动窗口的收缩
int left=0;
for(int right=0;right<m;right++){//移动子串右端点
cntS[SChar[right]]++;//右端点字母进入子串
while(isCovered(cntS,cntT)){//涵盖
if(right-left<ansRight-ansLeft){//找到了更短的子串
ansLeft=left;
ansRight=right;
}
cntS[SChar[left]]--;//左端点字母移出子串
left++;
}
}
return ansLeft<0?"":s.substring(ansLeft,ansRight+1);为什么ansLeft要初始化成-1？
因为我们要是初始化成0的话，我们并不能判断是否找到了满足条件的子串，因为我们的最终的return函数是根据0来判断，我们是否移动了指针（即是否找到了一个满足条件的子串）
看看我们的return
return ansLeft<0?"":s.substring(ansLeft,ansRight+1);代码
class Solution {
public String minWindow(String s, String t) {
char[] SChar = s.toCharArray();//子串的数组
int m=s.length();//子串的长度
int ansLeft=-1;
int ansRight=m;
int[] cntS=new int[128];//s子串的字母出现次数,s是子串
int[] cntT=new int[128];//t字符串中字母出现的次数,t是父串
//对父串中的字符的值进行初始化
for(char c:t.toCharArray()){
cntT[c]++;
}
int left=0;
for(int right=0;right<m;right++){//移动子串右端点
cntS[SChar[right]]++;//右端点字母进入子串
while(isCovered(cntS,cntT)){//涵盖
if(right-left<ansRight-ansLeft){//找到了更短的子串
ansLeft=left;
ansRight=right;
}
cntS[SChar[left]]--;//左端点字母移出子串
left++;
}
}
return ansLeft<0?"":s.substring(ansLeft,ansRight+1);
}
//如果父串里面的字符比子串多,我们返回false,说明这个子串并没有涵盖父串的所有字符
//如果子串里的字符数量都比子串多,那么说明这个子串没问题,这个子串涵盖了父串中的所有字符
private boolean isCovered(int[] cntS,int[] cntT)
{
for(int i='A';i<='Z';i++){
if(cntS[i]<cntT[i]){
return false;
}
}
for(int i='a';i<='z';i++){
if(cntS[i]<cntT[i]){
return false;
}
}
return true;
}
}