0 : result; } }; 时间复杂度：O(n^2) 空间复杂度：O(1) 滑动窗口 接下来就开始介绍数组操作中另一个重要的方法：「滑动窗口」。...所谓滑动窗口，「就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果」。 这里还是以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程： ?...其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。 在本题中实现滑动窗口，主要确定如下三点： 窗口内是什么？...窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。 解题的关键在于 窗口的起始位置如何移动，如图所示： ?...// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件 while (sum >= s) { subLength =
滑动窗口 暴力破解的思想是没问题的，但是缺点就在于每次 right 走完之后都需要回退，这就导致 O(n^2) 的时间复杂度，所以我们要想办法看看能不能让 left 和 right 都是不回退，一直向后走的...那么怎么利用呢❓❓❓ 此时一种算法思想：“滑动窗口”，就由此诞生了，不要觉得听起来很高级，其实 就是一种双指针的遍历方式，看起来很像一个窗口在动罢了！ ...切记，我们不要想着如何使用 “滑动窗口” 来解决问题，而是要思考，为什么要用 “滑动窗口”❓❓❓ 因为 “滑动窗口” 的核心就是控制窗口的左右边界进行出入窗口，其达到的效果就是让两个指针只需要遍历一次就能处理完问题...但是使用 “滑动窗口” 是有限制条件！ 对于这道题来说，只要出现了满足要求的组合之后，根据单调性，后续的长度就会增大，那么就没有遍历意义了！...这样子通过双指针的移动，看起来就像是一个窗口在平移，所以才叫做 “滑动窗口”！
题目 给定一个非空且只包含非负数的整数数组 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
滑动窗口（Sliding Window）是一种高效解决数组或字符串中子数组（子串）问题的算法技巧。它通过在数组上维护一个窗口（区间），动态地调整窗口的大小和位置，从而高效地解决问题。...本文将详细介绍滑动窗口算法的原理、实现及其应用。 一、算法原理 滑动窗口算法通过在数组上维护一个窗口来解决子数组问题。窗口的大小和位置可以动态调整，以满足不同问题的需求。...数组处理：如查找和大于等于目标值的最小子数组、固定大小的最大或最小子数组和等。 数据流处理：滑动窗口算法可以用于实时处理数据流，计算动态窗口内的数据特征。...四、总结 滑动窗口算法是一种高效解决数组或字符串中子数组（子串）问题的算法技巧，通过动态调整窗口的大小和位置，可以在O(n)时间复杂度内解决许多实际问题。...理解和掌握滑动窗口算法，可以有效解决字符串处理、数组处理和数据流处理等问题。
乘积小于k的子数组 给定一个正整数数组 nums和整数 k 。 请找出该数组内乘积小于 k 的连续的子数组的个数。...（意思是 我好像懂了滑动窗口 但是写的不规律不条理 好像没完全懂。。）...，k是指乘积需要小于的那个数，ans是指要求解的子数组的个数，l、r是指左右指针。...让我们来想一想，我们需要满足的条件是连续数组内的数乘积小于k，当右指针一直向右移动使得乘积不断增大时，总会有大于等于k的时候，那个时候，我们就需要改变l了，在这种情况下，我们计算的ans就不是现在的r-l...l不变、r向右移动时，我们的乘积一直都是非递减的，如果当前右指针移动到的位置使得l到r不满足乘积小于k，那我们再继续移动右指针，乘积一定依旧不满足小于k，那就说明这个l我们已经“利用”完了，l可以退出滑动窗口了
题目 当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组： 若 i A[k+1]，且当 k 为偶数时...也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。 返回 A 的最大湍流子数组的长度。...思路 暴力大法一堆if else判断所有条件，用一个jud判断这个窗口是第一个元素比第二个元素大还是小 class Solution { public: int maxTurbulenceSize
当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组： 若 i A[k+1]，且当 k 为偶数时，A...也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。 返回 A 的最大湍流子数组的长度。...4,8,12,16] 输出：2 示例 3： 输入：[100] 输出：1 提示： 1 <= A.length <= 40000 0 <= A[i] <= 10^9 解题思路： 1，题目意思翻译：连续呈波浪线增减的数组长度最大值
给定一个含有 n 个正整数的数组和一个正整数 target 。...找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。...如果不存在符合条件的子数组，返回 0 。...腾讯微信搜索团队一面的题，一模一样，用两个指针记录滑动窗口的头和尾巴，sum记录和，当sum大于等于target的时候，记录最小长度，将滑动窗口缩短至sum小于target class Solution
前言 当我们发现暴力解法两个指针都不回退，都是向同一个方向移动的时候我们就可以使用滑动窗口 1. 长度最小的子数组 题目链接： 209....，先用sum来统计以left为左区间的所有子数组的和，什么意思呢？...，我们可以直接更新sum的值 解法2：同向双指针（滑动窗口） 由解法1我们可以看出：本题的两个指针但是同一个方向进行移动的，那么我们就可以利用单调性，使用同向双指针（滑动窗口）来进行优化...如何使用滑动窗口： 1....定义两个指针left和right来充当窗口的左端点和右端点，然后用left和right来标记窗口的左区间和右区间 2. 进窗口 3.
题目 给定一个含有 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
问题描述：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。...比如s=7,nums=[2,3,1,2,4,3]，输出2，因为字数组[4,3]满足条件 class Solution: def minSubArrayLen(self, s, nums):...return len(nums) #步长i从1到len(nums)+1 for i in range(1,len(nums)+1): #j:表示窗口左端...for j in range(len(nums)-i+1): #如果当前窗口的和大于等于s，直接返回就步长就好了
滑动窗口推导过程 我们不能说一上来就知道这个题目用滑动窗口，然后就使用滑动窗口的方法来做这个题目。 首先我们想到的应该是暴力解法。 接着再优化为滑动窗口 由于数字都是 ≥ 0 的数。...而我们发现 (使用暴力解法的时候两个指针可以不会退。就可以用滑动窗口了) 此时只需要让sum-2 然后再次判断。就可以了。而right不用移动。 这就引入了滑动窗口。...滑动窗口的使用： 1. left = 0，right =0； 2.进窗口 3.判断 4.出窗口 方法一：暴力解法 class Solution { public int minSubArrayLen...: O(1)O(1)O(1)（只使用了常量级别的额外空间） 解法二：滑动窗口（利用单调性+ “同向双指针”） 1.left = 0，right = 0 2.进窗口。...使用while循环判断 4.出窗口：sum -= nums[left++]; 注意： 判断条件的时候一定要使用while循环。而不是if。 因为left++一次之后。也可能继续满足条件。
这道题我们就可以轻易分析可以使用滑动窗口来解决了 方法一：滑动窗口 这里注意 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]]++; //进入窗口...; } return ret; } } 复杂度分析 时间复杂度：O（n）， 空间复杂度： 常见分析: 空间复杂度为 O(1)，因为哈希表是固定大小，额外空间使用与输入大小无关...严格分析: 如果字符数组 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结尾的子数组个数
一、题目解析 二、算法原理 解法1:暴力枚举出所有的子数组的和0(n^2) 这里有两个点要注意，第一，我们可以观察到当sum>=target时，继续枚举是没有意义的，因为我们要找的是最短子数组，所以我们只需要枚举到...第二点呢，我们在数组的遍历中需要维护好sum的值，当left移动过后，新的sum没必要在次遍历求和，只需要在之前的基础上减去之前left指向的值即可。...解法2:利用上面第一点的发现，我们可以使用“滑动窗口”也叫“同向双指针”优化暴力枚举 我们需要初始化几个变量，left(左区间)，right(右区间)，sum(元素求和)，len(元素长度) 通过进窗口...，判断，出窗口，更新结果(更新的位置顺序由对应的题目来决定，本题更新结果在判断过后就要进行) 时间复杂也很好分析，(right遍历)n+(left遍历)n = o(n) 这里可以根据思路来自己实现一下，...因为当len为INT_MAX时可以认为不存在最短数组小于等于tagent，所以这里要对len的值进行判断。 如果能帮到您能否留下一个免费的赞，这对我很有帮助，我们下期再见！
问题描述（等级：尉） 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。...例如，数组为[4,3,1,5,4,3,7,5]，窗口大小为5时: [4 3 1 5 4] 3 7 5 max = 5 4 [3 1 5 4 3] 7 5 max = 5 4 3 [1 5 4 3 7...] 5 max = 7 4 3 1 [5 4 3 7 5] max = 7 即窗口最大值数组为 result = {5, 5,7,7} 解答: 对于一道题，我一般会第一时间想到用暴力的方法来做，之后再来慢慢优化...result[index++] = max; } return result; } 注：可以左右拉动 大家想一个问题，例如对于刚才例题中的数组...并且这个队列是有序的，队首存放的总是队列中的最大值， 我以这道题来演示一下，我们用result[] 数组来存放窗口最大值。 1、result[0] = 5 ? 2、result[1] = 5; ?
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。...返回 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
题目 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。...用暴力法把每个窗口的平均数求出来会超时，第一个窗口的总和是所有数加起来，这个没办法简略，但是下一个窗口的总和是上一个窗口的总和减去一个数加上后一个数。...所以不用把窗口中所有数再求一遍和，利用上一个窗口求解 class Solution { public: double findMaxAverage(vector& nums, int
题目描述：给定一个数组，求和为k的最大子数组的长度，子数组是指连续的一段数组。 比如[1,-1,5,-2,-3],k=3，那么输出为4，因为1+-1+5+-2=3。...solution(a,k): #用于记录当前最大值 tmp = 0 #步长i从1到len(a)+1 for i in range(1,len(a)+1): #j:表示窗口左端...for j in range(len(a)-i+1): print(a[j:j+i]) #如果当前窗口的和为k，则当前最大值就是tmp和步长得最大值
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 找到放到新数组组里面
云服务器
ICP备案
对象存储
实时音视频
云直播
