frontpage做网站教程,建设网站的公司广州,wordpress开发,无锡专业制作网站标题#xff1a;【leetcode】双指针算法技巧——滑动窗口
水墨不写bug 正文开始#xff1a; 滑动窗口介绍 滑动窗口是一种常用的算法技巧#xff0c;用于解决一些涉及 连续子数组或子串 的问题。它的基本思想是 维护一个窗口#xff0c;通过 在窗口内移动 来寻找满…标题【leetcode】双指针算法技巧——滑动窗口
水墨不写bug 正文开始 滑动窗口介绍 滑动窗口是一种常用的算法技巧用于解决一些涉及 连续子数组或子串 的问题。它的基本思想是 维护一个窗口通过 在窗口内移动 来寻找满足特定条件的子数组或子串。 滑动窗口算法的步骤如下 初始化窗口的起始位置left和终止位置right。在每一步迭代中将窗口右移一位即将right加1并根据题目要求更新窗口的状态。如果窗口的状态满足题目给定的条件那么根据题目要求处理结果。如果窗口的状态不满足题目给定的条件那么将窗口左移一位即将left加1继续迭代。 滑动窗口算法的时间复杂度通常为O(n)其中n是数组或字符串的长度。它的优势在于可以将一些问题的时间复杂度从O(n^2)降低到O(n)。 四个必要步骤 滑动窗口的四个必要步骤 1入窗口 2判断 3出窗口 4更新结果 对于前三条它们的顺序一般相对彼此是固定的。更新结果的位置放在何处需要根据题意判断。 一长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [nums , nums 1, ... , nums r-1, nums r] 并返回其长度。如果不存在符合条件的子数组返回 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]
输出0提示 1 target 10^91 nums.length 10^51 nums[i] 10^5 进阶 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。 思路一 找出所有的情况遍历出所有sumk的情况分别求其长度找出最小的长度即可。 以用例 1 具体来说 [ 2 , 3 , 1 , 2 , 4 , 3 ] 创建left指针标记第一个元素创建一个right指针向后遍历同时将两指针之间的元素求和sum如果sumk将此时的len存入数组ret最终再找出ret中的最小值即可。 更优的算法从哪里来是从暴力算法优化而来的 思路二 从宏观上我们先让sum尽可能的和k的值相近这样才可能满足sum与k相等。假设我们此时确定了一个区间 为了满足条件 如果sum k,继续增加sun的值 如果sumk记录len挑最小的记录 如果sum k,则要减小sum的值 现在就是确定如何加任何减的问题了。由于区间是连续的不能有间断所以从习惯上选择从左向右遍历移动窗口。 这样我们就知道了 leftleft指针向后移动实现减小sum出窗口 rightright指针向后移动实现增加sum入窗口 参考代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size(),len INT_MAX,sum 0;/*将len初始化为很大的数防止被求最小值的实际长度干扰*/for(int left 0,right 0;right n;right){//进窗口sum维护sum nums[right];while(sum target)//判断{len min(len,right-left 1);//更新结果sum - nums[left];//出窗口 }}return len INT_MAX ? 0 : len;}
}; 二无重复字符的最长字串 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是abc所以其长度为 3。示例 2: 输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是b所以其长度为 1。示例 3: 输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。 提示 0 s.length 5 * 10^4s 由英文字母、数字、符号和空格组成 让滑动窗口满足窗口内所有元素都是不重复的。 做法右端元素 ch 进⼊窗口的时候哈希表统计这个字符的频次 ▪ 如果这个字符出现的频次超过 1 说明窗口内有重复元素那么就从左侧开始划出窗口 直到 ch 这个元素的频次变为 1 然后再更新结果。 ▪ 如果没有超过 1 说明当前窗口没有重复元素可以直接更新结果。 参考代码
class Solution {
public:int lengthOfLongestSubstring(string s) {int left 0,right 0,n s.size(),ret 0;int hash[128] {0};//使用数组模拟哈希表while(right n){hash[s[right]];//进入窗口//判断while(hash[s[right]] 1){hash[s[left]]--;//出窗口}ret max(ret,right - left 1);right;}return ret;}
}; 三最大连续1的个数 给定一个二进制数组 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。 提示 1 nums.length 10^5nums[i] 不是 0 就是 10 k nums.length 不要自找麻烦思路其实很简单 要换个角度思考- 这道题的结果无非就是⼀段连续的 1 中间塞了 k 个 0 嘛。 我们可以把问题转化成求数组中一段最长的连续区间要求这段区间内 0 的个数不超过 k 个。 参考代码 class Solution {
public:int longestOnes(vectorint nums, int k) {int hash[2] {0};int n nums.size(),ret 0;//if(k n) return n;for(int right 0,left 0 ; right n ; right){hash[ nums[right] ];//进窗口while(hash[0] k)//判断{hash[ nums[left] ]--;//出窗口}ret max(ret,right-left1);}return ret;}
}; 四将x减小到0的最小操作数 给你一个整数数组 nums 和一个整数 x 。每一次操作时你应当移除数组 nums 最左边或最右边的元素然后从 x 中减去该元素的值。请注意需要 修改 数组以供接下来的操作使用。 如果可以将 x 恰好 减到 0 返回 最小操作数 否则返回 -1 。 示例 1 输入nums [1,1,4,2,3], x 5
输出2
解释最佳解决方案是移除后两个元素将 x 减到 0 。示例 2 输入nums [5,6,7,8,9], x 4
输出-1示例 3 输入nums [3,2,20,1,1,3], x 10
输出5
解释最佳解决方案是移除后三个元素和前两个元素总共 5 次操作将 x 减到 0 。提示 1 nums.length 10^51 nums[i] 10^41 x 10^9 题目要求的是数组「左端右端」两段连续的、和为 x 的最短数组 换一个角度思考- 我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最长数组。此时就是熟 悉的「滑动窗口」问题了 本质和 一长度最小的子数组 是相同的代码结构就一点不同——需要记录的数组长度从记录最小变成了记录最大。 参考代码
class Solution {
public:int minOperations(vectorint nums, int x) {int sum_all 0,n nums.size();for(int i 0;i n;i){sum_all nums[i];}int target sum_all - x,sum 0,left 0,right 0,ret -1;if(target 0) return n;for(;right n;right){sum nums[right];//进窗口if(sum target)//判断right最佳位置{while(sum target (left right)){sum - nums[left];//出窗口} }if(sum target){ret max(ret,right-left1);}}if(ret -1) return ret;else return n - ret;}
}; 完~
未经作者同意禁止转载
