leetcode滑动窗口问题

想成功先发疯不顾一切向前冲。第一种定长滑动窗口. - 力扣LeetCode1456.定长子串中的元音的最大数目. - 力扣LeetCodeNo.1定长滑窗套路我总结成三步入-更新-出。1. 入下标为 i 的元素进入窗口更新相关统计量。如果 ik−1 则重复第一步。2. 更新更新答案。一般是更新最大值/最小值。3. 出下标为 i−k1 的元素离开窗口更新相关统计量。以上三步适用于所有定长滑窗题目。class Solution { public int maxVowels(String S, int k) { char[] s S.toCharArray(); int ans 0; int temp 0; for (int i 0; i s.length; i) { // 1. 进入窗口 if (s[i] a || s[i] e || s[i] i || s[i] o || s[i] u) { temp; } if (i k - 1) { // 窗口大小不足 k continue; } // 2. 更新答案 ans Math.max(ans, temp); // 3. 离开窗口 char out s[i - k 1]; if (out a || out e || out i || out o || out u) { temp--; } } return ans; } }复杂度分析时间复杂度O(n)其中 n 是 s 的长度。空间复杂度O(1)。仅用到若干额外变量。这里对于字符串的处理及java的String类做一个详细说明toCharArray()是 Java 中String类的一个方法用于将字符串转换为字符数组 (char[])。每个字符数组中的元素对应于字符串中的一个字符。用法String str Hello, World!; char[] charArray str.toCharArray();解释str是一个String对象。调用str.toCharArray()会将字符串Hello, World!转换为一个字符数组。charArray将包含{H, e, l, l, o, ,, , W, o, r, l, d, !}常见用途字符串处理你可以更方便地遍历字符串中的每个字符。字符修改字符数组可以修改单个字符而String是不可变的即一旦创建不能更改其内容。1.length()作用: 返回字符串的长度字符数。示例:String str Hello, World!; int len str.length(); // len 132.charAt(int index)作用: 返回指定索引处的字符索引从 0 开始。示例:String str Hello; char ch str.charAt(1); // ch e3.substring(int beginIndex)/substring(int beginIndex, int endIndex)作用: 返回从指定索引开始或在索引区间内的子字符串。示例:String str Hello, World!; String subStr1 str.substring(7); // subStr1 World! String subStr2 str.substring(0, 5); // subStr2 Hello4.indexOf(String str)/indexOf(char ch)作用: 返回指定字符或子字符串在原字符串中第一次出现的索引若未找到则返回 -1。示例:String str Hello, World!; int index1 str.indexOf(W); // index1 7 int index2 str.indexOf(World); // index2 75.toUpperCase()/toLowerCase()作用: 返回将字符串转换为大写或小写后的新字符串。示例:String str Hello; String upperStr str.toUpperCase(); // upperStr HELLO String lowerStr str.toLowerCase(); // lowerStr hello6.trim()作用: 去除字符串开头和结尾的空白字符。示例:String str Hello, World! ; String trimmedStr str.trim(); // trimmedStr Hello, World!7.replace(char oldChar, char newChar)/replace(CharSequence target, CharSequence replacement)作用: 替换字符串中的指定字符或子字符串。示例:String str Hello, World!; String replacedStr1 str.replace(o, a); // replacedStr1 Hella, Warld! String replacedStr2 str.replace(World, Java); // replacedStr2 Hello, Java!8.equals(Object anObject)/equalsIgnoreCase(String anotherString)作用:比较两个字符串的内容是否相等。equalsIgnoreCase不区分大小写。示例:String str1 Hello; String str2 hello; boolean isEqual str1.equals(str2); // isEqual false boolean isEqualIgnoreCase str1.equalsIgnoreCase(str2); // isEqualIgnoreCase true9.split(String regex)作用: 根据正则表达式将字符串分割为子字符串数组。示例:String str apple,banana,orange; String[] fruits str.split(,); // fruits [apple, banana, orange]10.contains(CharSequence s)作用: 判断字符串是否包含指定的字符序列。示例:String str Hello, World!; boolean containsHello str.contains(Hello); // containsHello trueNo.2给你一个下标从 0 开始的整数数组nums其中nums[i]表示第i名学生的分数。另给你一个整数k。从数组中选出任意k名学生的分数使这k个分数间最高分和最低分的差值达到最小化。返回可能的最小差值。示例 1输入nums [90], k 1输出0解释选出 1 名学生的分数仅有 1 种方法 - [90] 最高分和最低分之间的差值是 90 - 90 0 可能的最小差值是 0示例 2输入nums [9,4,1,7], k 2输出2解释选出 2 名学生的分数有 6 种方法 - [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 5 - [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 8 - [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 2 - [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 3 - [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 3 - [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 6 可能的最小差值是 2class Solution { public int minimumDifference(int[] nums, int k) { Arrays.sort(nums); int len nums.length; int res Integer.MAX_VALUE; for (int i 0; i len - k; i) { res Math.min(res,nums[ik-1]-nums[i]); } return res; } }这个题要注意的地方是i 只有在 len-k 的条件下可以运行在后续的nums[ ]读数的时候左右节点要进行移动读数No.31343. - 力扣LeetCodeclass Solution { public int numOfSubarrays(int[] arr, int k, int threshold) { int len arr.length; int ans 0; for (int i 0; i k; i) { ans arr[i]; } int res 0; //很典型的一个坑初次忘记考虑当 i 0 取 k 个数的时候的 ans 的大小的判断 if(ansk*threshold){ res; } for (int i k; i len; i) { ans ans-arr[i-k] arr[i]; if(ans/kthreshold){ res; } } return res; } }不定长滑动窗口求最长或最大No.13.无重复字符的最长子串我认为思考的重点在于滑动窗口的起始位置与一般规律的总结我们不妨以示例一中的字符串 abcabcbb 为例找出从每一个字符开始的不包含重复字符的最长子串那么其中最长的那个字符串即为答案。对于示例一中的字符串我们列举出这些结果其中括号中表示选中的字符以及最长的字符串以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb以 abca(b)cbb 开始的最长字符串为 abca(bc)bb以 abcab(c)bb 开始的最长字符串为 abcab(cb)b以 abcabc(b)b 开始的最长字符串为 abcabc(b)b以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。class Solution { public int lengthOfLongestSubstring(String S) { int len S.length(); char[] s S.toCharArray(); SetCharacter hs new HashSet(); int res 0; for (int left 0, right 0; right len; right) { char ch s[right]; while (hs.contains(ch)) { hs.remove(s[left]); left; } hs.add(s[right]); res Math.max(res, right - left 1); } return res; } }right: 当前子串的右边界索引。left: 当前子串的左边界索引。子串的长度计算公式是右边界索引 - 左边界索引 1。寓意着包含左右边界的字符串No.21695.删除子数组的最大得分. - 力扣LeetCode给你一个正整数数组nums请你从中删除一个含有若干不同元素的子数组。删除子数组的得分 就是子数组各元素之 和 。返回 只删除一个 子数组可获得的 最大得分。如果数组b是数组a的一个连续子序列即如果它等于a[l],a[l1],...,a[r]那么它就是a的一个子数组。示例 1输入nums [4,2,4,5,6]输出17解释最优子数组是 [2,4,5,6]示例 2输入nums [5,2,1,2,5,2,1,2,5]输出8解释最优子数组是 [5,2,1] 或 [1,2,5]class Solution { public int maximumUniqueSubarray(int[] nums) { int len nums.length; // 获取数组的长度 SetInteger hs new HashSet(); // 创建一个 HashSet 用来存储当前子数组的元素 int res 0, ans 0; // res 用于存储当前子数组的元素和ans 用于存储最大得分 int i 0; // i 指针表示当前子数组的起点 // j 指针表示当前子数组的终点 for (int j 0; j len; j) { // 当 hs 中已经包含 nums[j] 时说明存在重复元素需要移动 i 指针 while (hs.contains(nums[j])) { hs.remove(nums[i]); // 从 HashSet 中移除子数组的第一个元素 res - nums[i]; // 从当前子数组的和中减去该元素的值 i; // 移动起点指针 i } hs.add(nums[j]); // 将 nums[j] 添加到 HashSet 中 res nums[j]; // 将 nums[j] 的值加到当前子数组的和中 ans Math.max(res, ans); // 更新最大得分 } return ans; // 返回只删除一个子数组可以获得的最大得分 } }No.3 上难度1004.最大连续1的个数III. - 力扣LeetCode给定一个二进制数组nums和一个整数k如果可以翻转最多k个0则返回数组中连续1的最大个数。示例 1输入nums [1,1,1,0,0,0,1,1,1,1,0], K 2输出6解释[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1最长的子数组长度为 6。示例 2输入nums [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K 3输出10解释[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1最长的子数组长度为 10。这个题有个特点就是数组内只有0 1那我们就围绕这一特点进行攻破及cnt 1 - nums[right];// 如果 nums[right] 是 0cnt 增加1如果是 1cnt 不变class Solution { public int longestOnes(int[] nums, int k) { int cnt 0; // 记录当前窗口内0的个数 int ans 0; // 记录最长的全1子数组的长度 int left 0; // 滑动窗口的左边界 // 右边界 right 从 0 开始遍历整个数组 for (int right 0; right nums.length; right) { cnt 1 - nums[right]; // 如果 nums[right] 是 0cnt 增加1如果是 1cnt 不变 // 如果当前窗口内的0的个数超过了允许的k个则需要收缩窗口 while (cnt k) { cnt - 1 - nums[left]; // 移动左边界移除 nums[left] 的影响 left; // 将左边界右移 } // 更新最长子数组的长度 ans Math.max(ans, right - left 1); } return ans; // 返回找到的最长的全1子数组的长度 } }class Solution { public int longestOnes(int[] nums, int k) { int len nums.length; int l 0, r 0; while(rlen){ if(nums[r]0) k--; if(k0 nums[l]0) k; } return r-l; } }No.4 方法一为1的最长子数组. - 力扣LeetCode给你一个二进制数组nums你需要从中删掉一个元素。(注意题目要求必须删除一个元素。也就说如果数组中全为 1也要删除一个 1。换句话说如果数组中不超过一个 0长度都为原数组长度减1只包含一个0将这个0删掉不包含0随便删一个元素)请你在删掉元素的结果数组中返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组请返回 0 。提示 1输入nums [1,1,0,1]输出3解释删掉位置 2 的数后[1,1,1] 包含 3 个 1 。示例 2输入nums [0,1,1,1,0,1,1,0,1]输出5解释删掉位置 4 的数字后[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。示例 3输入nums [1,1,1]输出2解释你必须要删除一个元素。做个简单的分析这道题要求删除一个元素得到最长连续 1 的子数组那么肯定希望把那些夹在 1 中间的 0 删掉。也就是说我们尝试删除每个 0 来看可以构成的最长连续 1 子数组而能够成最长连续 1一定是夹在两个 0 之间的范围。那么这道题的思路就和 1004. 最大连续1的个数 III。后者是替换 k 个 0参考 滑动窗口索引优化两个0之间有k个零 我们的做法是找到包含 k 个 0 的最长区间 (left, right)将里面的 0 都替换成 1长度即为 right - left - 1。而这道题要找的是包含 1 个 0 的最长区间 (left, right)将里面的 0 删除。长度就是原来的长度 right - left - 1 再减 1即 right - left - 2。实际上就是在 1004 题的方法上取 k 1【找到包含 1 个 0 的区间】那么长度的计算方式多减了 1。class Solution { public int longestSubarray(int[] nums) { ListInteger zeroIdxs new ArrayList(); // 记录数组中0元素的索引 int n nums.length; zeroIdxs.add(-1); // -1表示左边界 for(int i 0; i n; i){ if(nums[i] 0)zeroIdxs.add(i); } zeroIdxs.add(n); // n表示右边界 if(zeroIdxs.size() 3) return n - 1; // 数组中0的个数不超过1个直接删除唯一0或任意元素整个数组都为连续1 int m zeroIdxs.size(); int res 0; for(int i 2; i m; i){ // 枚举每个滑动窗口右边界i左边界就为i - 2保证(i,j)之间有1个0 // (i, j)本来有j - i - 1个数还要删掉一个0长度即为 j - i - 2 res Math.max(res, zeroIdxs.get(i) - zeroIdxs.get(i - 2) - 2); } return res; } }No.4 推荐方法二左右指针贪吃蛇思路胃口大小为k1遇到0则吃胃口饱后每前移一位就拉一位若拉出的是0则恢复1胃口最后算长度class Solution { public int longestSubarray(int[] nums) { int len nums.length; // 获取数组的长度 int l 0, r 0, k 1; // 初始化左右指针l和r以及可删除的0的数量k // 遍历数组 while (r len) { if (nums[r] 0) k--; // 如果右指针所指元素是0则k减1同时右指针右移 if (k 0 nums[l] 0) k; // 如果k小于0且左指针所指元素是0则k加1同时左指针右移 } return r - l - 1; // 返回最长子数组长度-1是因为需要删除一个元素 } }初始化l和r是左右指针用于维护一个滑动窗口k是允许删除的0的数量初始值为1因为我们允许删除一个0。遍历数组用r指针遍历整个数组每次遇到0我们将k减 1。当k变为负数时说明我们已经删除了超过允许数量的0这时就需要移动l指针来缩小窗口。调整窗口当k小于0时说明窗口内有多余的0需要移除因此我们移动l指针直到k恢复到非负状态。返回结果最终r - l - 1计算的是最大子数组的长度减 1 是因为题目要求删除一个元素。No.5 巩固一下. - 力扣LeetCodeclass Solution { public int longestSemiRepetitiveSubstring(String s) { int ans 1; // 初始化结果表示最长半重复子串的长度 int left 0; // 左指针表示当前子串的起始位置 int same 0; // 记录当前重复字符的对数 int n s.length(); // 获取字符串的长度 // 右指针从位置1开始遍历字符串 for (int right 1; right n; right) { // 如果当前字符与前一个字符相同 if (s.charAt(right) s.charAt(right - 1)) { same; // 增加重复字符对的计数 // 如果重复字符对超过1个 if (same 1) { // 移动左指针直到找到下一个重复字符对的起点 left; while (s.charAt(left) ! s.charAt(left - 1)) { left; } same 1; // 重置重复字符对的计数 } } // 更新最长半重复子串的长度 ans Math.max(ans, right - left 1); } return ans; // 返回最长半重复子串的长度 } }不定长滑动窗口求最短/最小No.1209.长度最小的子数组. - 力扣LeetCode给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl, numsl1, ..., numsr-1, numsr]并返回其长度。如果不存在符合条件的子数组返回0。示例 1输入target 7, nums [2,3,1,2,4,3]输出2解释子数组[4,3]是该条件下的长度最小的子数组。示例 2输入target 4, nums [1,4,4]输出1示例 3输入target 11, nums [1,1,1,1,1,1,1,1]输出0class Solution { public int minSubArrayLen(int target, int[] nums) { int n nums.length; // 获取数组的长度 int ans n 1; // 初始化结果为 n 1表示一个不可能达到的最大长度为了后面比较 int sum 0; // 当前子数组的和 int left 0; // 子数组的左边界起始为0 // 使用滑动窗口方法遍历数组 for (int right 0; right n; right) { sum nums[right]; // 将右边界的元素加到当前子数组的和中 // 当当前子数组的和大于等于目标值时尝试缩小窗口 while (sum target) { // 更新答案为当前子数组长度的最小值 ans Math.min(ans, right - left 1); // 从左边界开始缩小窗口 sum - nums[left]; } } // 如果找到了有效的子数组返回最小长度否则返回0 return ans n ? ans : 0; } }解释变量ans用于存储当前找到的满足条件的最小子数组长度。代码执行时它初始化为n 1比数组最大可能长度大1的一个值这个初始值用来保证在后续计算中如果找不到满足条件的子数组结果能被正确判断为无效因为不可能有子数组长度大于数组本身的长度。ans的更新逻辑如下每当子数组的和sum大于或等于目标值target时当前子数组的长度right - left 1可能是一个新的候选解。通过ans Math.min(ans, right - left 1)语句代码在找到新的更短的子数组时更新ans。最后ans只有在它小于等于n时才会被返回表示找到了一组符合条件的子数组否则返回0表示没有找到这样的子数组。不定长滑动窗口求子数组个数No.1713.乘积小于K的子数组. - 力扣LeetCodeclass Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { // 如果 k 小于或等于 1不可能有乘积小于 k 的子数组 if (k 1) return 0; int len nums.length; int left 0; // 滑动窗口的左边界 int product 1; // 当前窗口内元素的乘积 int count 0; // 满足条件的子数组数量 // 遍历数组的每个元素作为窗口的右边界 for (int right 0; right len; right) { product * nums[right]; // 乘上当前元素 // 如果乘积大于等于 k缩小窗口的左边界直到乘积小于 k while (product k) { product / nums[left]; // 移除左边界元素的影响 left; // 左边界右移 } // 统计以 nums[right] 结尾的、乘积小于 k 的子数组数量 count right - left 1; } return count; // 返回总的满足条件的子数组数量 } }还算好理解咱们一起看下一道菜多指针滑动窗口No.1. - 力扣LeetCode2563.统计公平数对的数目给你一个下标从0开始、长度为n的整数数组nums和两个整数lower和upper返回公平数对的数目。如果(i, j)数对满足以下情况则认为它是一个公平数对0 i j n且lower nums[i] nums[j] upper示例 1输入nums [0,1,7,4,4,5], lower 3, upper 6输出6解释共计 6 个公平数对(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。示例 2输入nums [1,7,9,2,5], lower 11, upper 11输出1解释只有单个公平数对(2,3) 。class Solution { public long countFairPairs(int[] nums, int lower, int upper) { Arrays.sort(nums); int left nums.length, right left; long ans 0; for (int i 0; i nums.length; i) { while (right 0 nums[right - 1] upper-nums[i]) { right--; } while (left 0 nums[left - 1] lower-nums[i]) { left--; } ans Math.min(right, i) - Math.min(left, i); } return ans; } }完结