题目 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。...示例 1： 输入：[1, 2, 2, 3, 1] 输出：2 解释： 输入数组的度是2，因为元素1和2的出现频数最大，均为2....连续子数组里面拥有相同度的有如下所示: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] 最短连续子数组...思路 用map把数组中出现的数个数记录下来，然后找到最大度和出现频数最大的那个数m，与原始数组度相同的子数组必然包含所有的m，那么如果要求最短的子数组就是求包含所有m的最短数组。...有个需要注意的地方就是m可以是多个，所以就要把每个m存到一个数组中然后把所有m对应的最短子数组的长度求出取最小 class Solution { public: int result(int m
乘积小于k的子数组 给定一个正整数数组 nums和整数 k 。 请找出该数组内乘积小于 k 的连续的子数组的个数。...先敲个黑板 下面一共有两种写法，第一种是按自己理解写的，是过了的，但是 感觉懂了但没完全懂。。。（意思是 我好像懂了滑动窗口 但是写的不规律不条理 好像没完全懂。。）...，k是指乘积需要小于的那个数，ans是指要求解的子数组的个数，l、r是指左右指针。...因为我们计算的是连续的子数组的个数，每次右指针移动、加入一个新的右边的数值的时候，在满足l到r的乘积小于k的前提下，总的ans的增加量就是新的值、新的值与之前所有可连续的值的组合，这个就用到一点点数学知识了...因为当l不变、r向右移动时，我们的乘积一直都是非递减的，如果当前右指针移动到的位置使得l到r不满足乘积小于k，那我们再继续移动右指针，乘积一定依旧不满足小于k，那就说明这个l我们已经“利用”完了，l可以退出滑动窗口了
给定一个含有 n 个正整数的数组和一个正整数 target 。...找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。...如果不存在符合条件的子数组，返回 0 。...腾讯微信搜索团队一面的题，一模一样，用两个指针记录滑动窗口的头和尾巴，sum记录和，当sum大于等于target的时候，记录最小长度，将滑动窗口缩短至sum小于target class Solution
题目 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。 如果不存在符合条件的连续子数组，返回 0。...示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。...滑动窗口解题 贪心思想 总和大了，sum减去左边界，左端边界+1 总和小了，右边界+1，sum加上右边界 class Solution { //C++ public: int minSubArrayLen
前言 当我们发现暴力解法两个指针都不回退，都是向同一个方向移动的时候我们就可以使用滑动窗口 1. 长度最小的子数组 题目链接： 209....，先用sum来统计以left为左区间的所有子数组的和，什么意思呢？...，再计算数组走了几步，后面的就没有必要继续计算了，因为题目要求的是最小长度的子数组 接下来我们再将left往后移动一位，然后我们的right是可以不需要移动的，因为我们上面已经知道[...3 ~ 2] 这个区间的值为多少，我们可以直接更新sum的值 解法2：同向双指针（滑动窗口） 由解法1我们可以看出：本题的两个指针但是同一个方向进行移动的，那么我们就可以利用单调性，...使用同向双指针（滑动窗口）来进行优化 如何使用滑动窗口： 1.
滑动窗口推导过程 我们不能说一上来就知道这个题目用滑动窗口，然后就使用滑动窗口的方法来做这个题目。 首先我们想到的应该是暴力解法。 接着再优化为滑动窗口 由于数字都是 ≥ 0 的数。...right 还需要从新回到left的位置。再次计算累加和是否≥target。 而我们发现 (使用暴力解法的时候两个指针可以不会退。就可以用滑动窗口了) 此时只需要让sum-2 然后再次判断。...这就引入了滑动窗口。 利用单调性，+同向双指针。...滑动窗口的使用： 1. left = 0，right =0； 2.进窗口 3.判断 4.出窗口 方法一：暴力解法 class Solution { public int minSubArrayLen...n是数组的长度。指针 left 和 right 最多各移动一次。 空间复杂度：O（1）。
有了上一篇的基础。...这道题我们就可以轻易分析可以使用滑动窗口来解决了 方法一：滑动窗口 这里注意 ret 在while循环外部更新 在 while 外部更新 ret，确保窗口在满足条件后再计算长度，避免错误计入正在调整中的窗口长度...Solution { public int lengthOfLongestSubstring(String s0) { int[] hash = new int[128]; //数组模拟哈希表...ret = 0; for(int left = 0,right = 0; right < n; right++){ hash[s[right]]++; //进入窗口...严格分析: 如果字符数组 chars 被视为额外空间，则空间复杂度为 O(n)
题目 给定一个正整数数组 nums。 找出该数组内乘积小于 k 的连续的子数组的个数。...示例 1: 输入: nums = [10,5,2,6], k = 100 输出: 8 解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2],...需要注意的是 [10,5,2] 并不是乘积小于100的子数组。...解题 滑动窗口，连续乘积 < k，右端点向右扩 乘积 >= k，左端点向右收缩 class Solution { //C++ public: int numSubarrayProductLessThanK...product*nums[j] < k) { //右端点一直乘 product *= nums[j]; count += j-i+1;//以j结尾的子数组个数
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。...（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。） 返回 A 中好子数组的数目。...示例 2： 输入：A = [1,2,1,3,4], K = 3 输出：3 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4]....提示： 1 <= A.length <= 20000 1 <= A[i] <= A.length 1 <= K <= A.length 解题思路： 1，这是一个滑动窗口类题目，设置左右指针start,end...2,窗口内部问题可以拆分出两个子问题 A，K种不同值组成的子数组 B，A所得子数组中，移动左指针仍然满足题目要求的子数组 3，定义两个左指针start，start2 A，移动start和end，直到k
return result; } } 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置...] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 思路: 1 开一个新数组...存放最大值 2 两个循环 ,第一个控制走到最后,第二个来实现寻找最大值,(k范围内的)(借助Math.max) 比较(i+1,k-1) 3 找到放到新数组组里面
双端队列实现 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。...返回滑动窗口中的最大值。...输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 ----...5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 思路 : 1 开一个双端队列 和一个结果数组...(存储结果最大值的) 2 只需要把双端队列第一个设置为最大值 3 每一次满足窗口大小就 返回第一个Nums[ 队列里面的第一个值] 4 刚开始的话是要满足 队列里面填充k 个 5 满了之后,随着窗口易懂
前言 声明：题目来源于： 力扣 一、长度最小的子数组 题目链接：传送门 (1) 题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。...找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。...如果不存在符合条件的子数组，返回 0 。...示例： 示例 1： 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释： 子数组 [4,3] 是该条件下的长度最小的子数组。...如果left+right>=target,表示窗口满足条件,可以统计窗口的长度，更新最短长度，需要注意的是，这里出窗口是循环的，只要窗口内元素之和sum>=target，则我们可以继续出窗口（因为我们要求最短长度
我们可以使用两个指针当做数组的左右区间，用left，right指针指向数组的下标，left表示左区间，right表示右区间，用sum值计算每次移动区间之后区间元素值的和，最后遍历完返回最小区间数组。...————滑动窗口 解法二： 思路： 其实整体思路和上面差不多，不过滑动窗口的left和right都是在向右移动，right指针没有回退的操作，这种“同向双指针” ，也被称为滑动窗口，其实很形象，...左右指针一直同向移动，看起来就像是在滑动的窗口，故此得名。 ...我们可以看到，如果是最坏的情况，也就是左右指针把数组都遍历一遍，也就是O(2n)时间复杂度，也就是 O(N) 级别的时间复杂度，空间上只用了几个变量，所以 空间复杂度为O(1)，相比较之下，我们的滑动窗口确实非常好用...0 : len; } }; 今天是第一次写滑动窗口的题，果然非常奇妙，居然只有O(N)的时间复杂度，理解滑动窗口的本质才有助于你解决类似问题不会毫无思路。
题目 给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。...（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。） 返回 A 中好子数组的数目。...示例 1： 输入：A = [1,2,1,2,3], K = 2 输出：7 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2...示例 2： 输入：A = [1,2,1,3,4], K = 3 输出：3 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4]....而「最多存在 KK 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 K - 1K−1 个不同整数的子区间的个数」。
题目 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。...难易程度：easy 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 [1 3 -1] -3 5...[-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 提示： 你可以假设 k 总是有效的，...在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。...题解 分析 通过分析，索引[i - k, i)之间的k个元素的最大值max的索引max_index存在max_index > i - k && max_index = nums
今天给大家分享一道 facebook 的面试题，也就是 Leetcode 209. 长度最小的子数组，提供滑动窗口解题思路，供大家参考。...滑动窗口解法： 假设下标从 i 到 j 连续子数组元素和为 sum，如下图示： ? 如果当前的 sum 小于 s，则将下标 j 右移，将其后面一个数组元素也加入到 sum 中，如下如示： ? ?...整个过程一直保持着一个窗口，其长度不是固定的，但是是被 i 和 j 这两个索引所定义的，窗口不停向前滑动去寻找满足题意的连续子数组。...Code // c 语言版本 int minSubArrayLen(int s, int* nums, int numsSize){ int sum = 0; // 窗口中数组元素的和...为滑动窗口 while (left < numsSize) { // sum 小于 s，窗口的右边界向前拓展，但要保证右边界 right 不越界 if ((right
题目 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。...如果不存在满足条件的子数组，则返回 0 。...因此，满足题意的最长子数组的长度为 2 。...], limit = 0 输出：3 提示： 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^9 0 <= limit <= 10^9 思路 根据题意可以理解为子数组必须满足当前子数组最大值和最小值的差小于等于...limit，所以可以采用multiset方便求子数组的最大值和最小值，当不满足情况时将窗口的最左边一一剔除直到满足，所以要用到双指针。
LeetCode209.滑动窗口算法原理图解(Kotlin语言):长度最小的子数组 题目: 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 sum ≥ s 的长度最小的连续子数组...进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 滑动窗口的算法原理图解 ?...s ，找出该数组中满足其和 sum ≥ s 的长度最小的连续子数组。...= Int.MAX_VALUE) ans else 0 } /** * 滑动窗口: * 解题思路 思路： 当输出或比较的结果在原数据结构中是连续排列的时候，可以使用滑动窗口算法求解。...将两个指针比作一个窗口，通过移动指针的位置改变窗口的大小，观察窗口中的元素是否符合题意。 初始窗口中只有数组开头一个元素。 当窗口中的元素小于目标值，右指针向右移，扩大窗口。
绝对差不超过限制的最长连续子数组题解集合 暴力法 滑动窗口和双指针 利用单调队列找出当前滑动窗口的最大最小值 单调队列的优化思路 总结 ---- 暴力法 思路:列举出所有满足条件的子数组，从中找出最大的长度...; } } return maxLen; } }; ---- 滑动窗口和双指针 思路: 使用滑动窗口保持符合条件的子数组，记录最长长度 怎样确定子数组是否符合条件，需要知道两个关键数据...，就把队尾元素依次出队，直到前面的元素比当前要放入的元素小为止 以上的步骤可以保证单调增队列的首元素永远是当前滑动窗口的最大值，单调减队列的首元素是当前滑动窗口的最小值 如果当前滑动窗口内的最大值减去最小值得到的结果比限制值要大...Max.empty() && Max.back() < num) Max.pop_back(); Max.push_back(num); //让滑动窗口左端指针移动到当前滑动窗口内的子数组满足题目要求为止...思路: 参考滑动窗口和双指针解法，这里只需要确保在未找到更大连续子数组长度的时候，滑动窗口的大小等于当前最长连续子数组长度 做法: //判断当前i指向位置的元素是否是当前滑动窗口内的最大值或者最小值，
个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。...不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。...找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。...示例 2：输入：target = 4, nums = [1,4,4]输出：1示例 3：输入：target = 11, nums = [1,1,1,1,1,1,1,1]输出：04.3、题解使用滑动窗口法，...本质上也是双指针的操作，tmplength记录滑动窗口目前的大小（用right-left其实也可以直接计算），sum记录滑动窗口当前的和值，minlength记录最小的窗口大小。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
云直播
对象存储
实时音视频
