东莞品牌型网站建设价格,网站开发技术题目,推广公司名字,室内设计理念滑动窗口 要区分最小和最大滑窗#xff0c;内层while循环的条件和更新结果的地方 核心#xff1a;
关键的区别在于#xff0c;最大滑窗是在迭代右移右边界的过程中更新结果#xff0c;而最小滑窗是在迭代右移左边界的过程中更新结果。
最小滑窗
给定数组 nums#xff0…滑动窗口 要区分最小和最大滑窗内层while循环的条件和更新结果的地方 核心
关键的区别在于最大滑窗是在迭代右移右边界的过程中更新结果而最小滑窗是在迭代右移左边界的过程中更新结果。
最小滑窗
给定数组 nums定义滑窗的左右边界 i, j求满足某个条件的滑窗的最小长度。
while j len(nums)://这个while也可用fori代替判断[i, j]是否满足条件while 满足条件不断更新结果(注意在while内更新)i 1 最大程度的压缩i使得滑窗尽可能的小j 1L209长度最小的子数组 题目给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。 示例 输入s 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。 提示 1 target 10^91 nums.length 10^51 nums[i] 10^5 class Solution {// 滑动窗口public int minSubArrayLen(int s, int[] nums) {int left 0;int sum 0;int result Integer.MAX_VALUE;for (int right 0; right nums.length; right) {sum nums[right];//这里要求的是最小子数组所以这里的while是满足条件的//然后在while里面最大程度的压缩i也就是左边界while (sum s) {result Math.min(result, right - left 1);sum - nums[left];}}return result Integer.MAX_VALUE ? 0 : result;}
}最大滑窗
给定数组 nums定义滑窗的左右边界 i, j求满足某个条件的滑窗的最大长度。
while j len(nums):判断[i, j]是否满足条件while 不满足条件i 1 最保守的压缩i一旦满足条件了就退出压缩i的过程使得滑窗尽可能的大不断更新结果注意在while外更新j 1L904水果成蓝 你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果 你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。 一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。 给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。 白话题目求只包含两种元素的最长连续子序列 class Solution {public int totalFruit(int[] fruits) {int n fruits.length;MapInteger, Integer cnt new HashMapInteger, Integer();int left 0, ans 0;for (int right 0; right n; right) {cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) 1);//注意这里的while是不满足条件的//并且这里统计的ans是在while外面进行更新的//这个与上面的最小子数组有着本质区别while (cnt.size() 2) {cnt.put(fruits[left], cnt.get(fruits[left]) - 1);if (cnt.get(fruits[left]) 0) {cnt.remove(fruits[left]);}left;}ans Math.max(ans, right - left 1);}return ans;}
}总结 第一题让求大于某个数的最小子数组长度 while里面最大限度的压缩只要满足就压缩 while的条件是大于某个数即满足题意并且while每循环一次就更新一下result的长度 while (sum s) {result Math.min(result, right - left 1);sum - nums[left];}第二题让求最多包含两类2的最长子序列长度 while里面最小程度的压缩 while里的条件是大于2即与题意相反并且是while结束后进行更新长度ans while (cnt.size() 2) {cnt.put(fruits[left], cnt.get(fruits[left]) - 1);if (cnt.get(fruits[left]) 0) {cnt.remove(fruits[left]);}left;}ans Math.max(ans, right - left 1);
