个人主页https://github.com/zbhgis前言本系列主要记录自己学习算法的过程中的感悟。力扣209. 长度最小的子数组链接https://leetcode.cn/problems/minimum-size-subarray-sum/description/注意点滑动窗口做法。这类题的注意点在于窗口长度的控制。1.定义两个指针右指针先移动移动到某个位置后满足题目所需的target条件之后也就是sum target之后开始尝试移动左指针缩小窗口。2.在第一步操作的过程中需要一个额外的sum变量来实时计算窗口的总和right前进就加上新的数left前进就减去这个数。代码class Solution { public int minSubArrayLen(int target, int[] nums) { int left 0; int sum 0; int len Integer.MAX_VALUE; for (int right 0; right nums.length; right ){ sum nums[right]; while (sum target) { len Math.min(len, right - left 1); sum - nums[left]; left ; } } return len Integer.MAX_VALUE ? 0 : len; } }时空复杂度分析虽然是双重循环但是由于内层和外层循环加起来总共访问2n最多所以最坏情况O(2n)O(n)空间复杂度O(1)力扣904. 水果成篮链接https://leetcode.cn/problems/fruit-into-baskets/description/注意点滑动窗口做法。1.类似于上一题这题需要额外创建一个数组来记录水果的类型。2.定义两个指针右指针先移动移动在某个某个位置后满足题目所需的水果类型只有两个之后进一步移动尝试移动右指针直到水果类型有三个就是type 2或者type 3的时候然后再移动左指针来收缩因为没办法精确地停下来缩小窗口。3.其他都类似就是写起来麻烦一些此时通过cnt数组来记录水果类型的个数作用类似于上一题的sum。4.还有就是记录类型种类type的时候开始记录种类的时候需要先cnt再type移除记录种类的时候则是先type再cnt代码class Solution { public int totalFruit(int[] fruits) { int left 0; int len 0; int type 0; int[] cnt new int[fruits.length]; for (int right 0; right fruits.length; right ) { int in fruits[right]; if (cnt[in] 0) type ; cnt[in] ; while (type 2) { int out fruits[left]; cnt[out] --; if (cnt[out] 0) type --; left ; } len Math.max(len, right - left 1); } return len; } }时空复杂度分析虽然是双重循环但是由于内层和外层循环加起来总共访问2n最多所以最坏情况O(2n)O(n)空间复杂度O(n)n为fruits的长度力扣76. 最小覆盖子串链接https://leetcode.cn/problems/minimum-window-substring/description/注意点滑动窗口做法。1.类似于上一题不过这题更难使用普遍的滑动窗口也能成功下面是优化版本。2.首先定义一个diff表示窗口每种字母个数 - t每种字母个数。第一步先获取到窗口为空的情况下两者的差异。之后类似于前两题开始定义两个指针。这题需要额外定义ansLeft 和ansRight因为这个题返回的是具体的数组不是长度了所以要考虑到最后窗口为空的情况。额外定义一个geCnt表示窗口内有geCnt种字母的出现次数 t中相应字母的出现次数。3.开始遍历右指针先移动对应的diff也随之更新。当diff[s[right]] 0的时候说明出现了新字符geCnt也随之更新。直到geCnt kinds说明现在符合题目所要求的字符个数了开始移动左指针。开始更新窗口长度用ansLeft 和 ansRight记录方便后续在循环外返回结果。代码class Solution { public String minWindow(String S, String t) { int[] diff new int[128]; int kinds 0; for (char c : t.toCharArray()) { if (diff[c] 0) { kinds ; } diff[c] --; } int left 0; char[] s S.toCharArray(); int m s.length; int ansLeft -1; int ansRight m; int geCnt 0; for (int right 0; right m; right ) { char c s[right]; diff[c] ; if (diff[c] 0) { geCnt ; } while (geCnt kinds) { if (right - left ansRight - ansLeft) { ansLeft left; ansRight right; } char x s[left]; if (diff[x] 0) { geCnt --; } diff[x] --; left ; } } return ansLeft 0 ? : S.substring(ansLeft, ansRight 1); } }时空复杂度分析虽然是双重循环但是由于内层和外层循环加起来总共访问2n最多所以最坏情况O(2n)O(n)空间复杂度O(128)即O(1)参考https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
