濮阳网站建设 公司名字用asp做网站课程

濮阳网站建设 公司名字,用asp做网站课程,建筑公司起名字寓意好的字,建设企业网站需要哪些东西滑动窗口是处理子串/子数组问题的经典双指针技巧#xff0c;核心是通过维护一个“窗口”#xff08;左右指针界定的区间#xff09;#xff0c;动态调整窗口范围来满足题目条件#xff0c;从而高效求解问题。 一、无重复字符的最长子串 题目描述#xff1a; 给定一个字符…滑动窗口是处理子串/子数组问题的经典双指针技巧核心是通过维护一个“窗口”左右指针界定的区间动态调整窗口范围来满足题目条件从而高效求解问题。一、无重复字符的最长子串题目描述给定一个字符串s找出其中不含有重复字符的最长子串的长度。示例输入s abcabcbb输出3最长子串为abc输入s bbbbb输出1最长子串为b解题思路用滑动窗口维护“无重复字符的子串”配合哈希数组记录字符出现次数定义窗口左右指针left、right哈希数组hash[128]统计窗口内字符出现次数。右指针right遍历字符串将当前字符加入窗口并更新出现次数。若当前字符出现次数超过1窗口内有重复移动左指针缩小窗口直到无重复。每次调整后更新最长子串长度。完整代码classSolution{public:intlengthOfLongestSubstring(string s){inthash[128]{0};intret0;for(intleft0,right0;rights.size();right){hash[s[right]];while(hash[s[right]]1){hash[s[left]]--;}retmax(ret,right-left1);}returnret;}};复杂度分析时间复杂度O(n)O(n)O(n)每个字符最多被左右指针各遍历一次。空间复杂度O(1)O(1)O(1)哈希数组大小固定128个ASCII字符。二、长度最小的子数组题目描述给定含n个正整数的数组和正整数target找出总和≥target的长度最小的子数组返回其长度若不存在则返回0。示例输入target 7, nums [2,3,1,2,4,3]输出2子数组[4,3]解题思路用滑动窗口维护“总和≥target的子数组”动态缩小窗口找最小长度定义窗口左右指针left、right变量sum记录窗口内元素和。右指针right遍历数组累加元素和到sum。若sum ≥ target尝试移动左指针缩小窗口同时更新最小长度直到sum target。遍历结束后若未找到符合条件的子数组则返回0。完整代码classSolution{public:intminSubArrayLen(inttarget,vectorintnums){intsum0,lenINT_MAX;for(intleft0,right0;rightnums.size();right){sumnums[right];while(sumtarget){lenmin(len,right-left1);sum-nums[left];}}returnlenINT_MAX?0:len;}};复杂度分析时间复杂度O(n)O(n)O(n)每个元素最多被左右指针各遍历一次。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。三、最大连续1的个数 III题目描述给定二进制数组nums和整数k最多可以翻转k个0返回操作后数组中连续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]解题思路用滑动窗口维护“最多包含k个0的子数组”即允许翻转k个0后的连续1区间定义窗口左右指针left、right变量zeros统计窗口内0的个数。右指针right遍历数组遇到0则zeros。若zeros k移动左指针缩小窗口直到zeros ≤ k。每次调整后更新最长子数组长度。完整代码classSolution{public:intlongestOnes(vectorintnums,intk){intret0;for(intleft0,right0,zeros0;rightnums.size();right){if(nums[right]0)zeros;while(zerosk){if(nums[left]0)zeros--;}retmax(ret,right-left1);}returnret;}};复杂度分析时间复杂度O(n)O(n)O(n)每个元素最多被左右指针各遍历一次。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。四、将x减到0的最小操作数题目描述给定整数数组nums和整数x每次操作移除数组最左或最右元素并从x中减去该元素值要求将x恰好减到0返回最小操作数否则返回-1。示例输入nums [1,1,4,2,3], x 5输出2移除后两个元素235解题思路转化问题“最小操作数”等价于“数组中最长的、和为sum(nums)-x的子数组”因为移除的元素是数组两端剩余的中间子数组和为sum-x。计算数组总和sum目标子数组和为target sum - x若target 0直接返回-1。用滑动窗口找最长的、和为target的子数组。若找到该子数组最小操作数为数组长度 - 子数组长度否则返回-1。完整代码classSolution{public:intminOperations(vectorintnums,intx){intsum0;for(auton:nums)sumn;inttargetsum-x;if(target0)return-1;intret-1;for(intleft0,right0,tmp0;rightnums.size();right){tmpnums[right];while(tmptarget)tmp-nums[left];if(tmptarget)retmax(ret,right-left1);}returnret-1?-1:nums.size()-ret;}};复杂度分析时间复杂度O(n)O(n)O(n)每个元素最多被左右指针各遍历一次。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。