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;}
}