【算法题】滑动窗口(一)

滑动窗口是处理子串/子数组问题的经典双指针技巧，核心是通过维护一个“窗口”（左右指针界定的区间），动态调整窗口范围来满足题目条件，从而高效求解问题。

一、无重复字符的最长子串

题目描述：
给定一个字符串s，找出其中不含有重复字符的最长子串的长度。

示例：

• 输入：s = "abcabcbb"，输出：3（最长子串为"abc"）
• 输入：s = "bbbbb"，输出：1（最长子串为"b"）

解题思路：
用滑动窗口维护“无重复字符的子串”，配合哈希数组记录字符出现次数：

1. 定义窗口左右指针left、right，哈希数组hash[128]统计窗口内字符出现次数。
2. 右指针right遍历字符串，将当前字符加入窗口并更新出现次数。
3. 若当前字符出现次数超过1（窗口内有重复），移动左指针缩小窗口，直到无重复。
4. 每次调整后，更新最长子串长度。

完整代码：

classSolution{public:intlengthOfLongestSubstring(string s){inthash[128]={0};intret=0;for(intleft=0,right=0;right<s.size();right++){hash[s[right]]++;while(hash[s[right]]>1){hash[s[left++]]--;}ret=max(ret,right-left+1);}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的子数组”，动态缩小窗口找最小长度：

1. 定义窗口左右指针left、right，变量sum记录窗口内元素和。
2. 右指针right遍历数组，累加元素和到sum。
3. 若sum ≥ target，尝试移动左指针缩小窗口（同时更新最小长度），直到sum < target。
4. 遍历结束后，若未找到符合条件的子数组则返回0。

完整代码：

classSolution{public:intminSubArrayLen(inttarget,vector<int>&nums){intsum=0,len=INT_MAX;for(intleft=0,right=0;right<nums.size();right++){sum+=nums[right];while(sum>=target){len=min(len,right-left+1);sum-=nums[left++];}}returnlen==INT_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区间）：

1. 定义窗口左右指针left、right，变量zeros统计窗口内0的个数。
2. 右指针right遍历数组，遇到0则zeros++。
3. 若zeros > k，移动左指针缩小窗口，直到zeros ≤ k。
4. 每次调整后，更新最长子数组长度。

完整代码：

classSolution{public:intlongestOnes(vector<int>&nums,intk){intret=0;for(intleft=0,right=0,zeros=0;right<nums.size();right++){if(nums[right]==0)zeros++;while(zeros>k){if(nums[left++]==0)zeros--;}ret=max(ret,right-left+1);}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（移除后两个元素2+3=5）

解题思路：
转化问题：“最小操作数”等价于“数组中最长的、和为sum(nums)-x的子数组”（因为移除的元素是数组两端，剩余的中间子数组和为sum-x）。

1. 计算数组总和sum，目标子数组和为target = sum - x（若target < 0，直接返回-1）。
2. 用滑动窗口找最长的、和为target的子数组。
3. 若找到该子数组，最小操作数为数组长度 - 子数组长度；否则返回-1。

完整代码：

classSolution{public:intminOperations(vector<int>&nums,intx){intsum=0;for(auton:nums)sum+=n;inttarget=sum-x;if(target<0)return-1;intret=-1;for(intleft=0,right=0,tmp=0;right<nums.size();right++){tmp+=nums[right];while(tmp>target)tmp-=nums[left++];if(tmp==target)ret=max(ret,right-left+1);}returnret==-1?-1:nums.size()-ret;}};

复杂度分析：

• 时间复杂度：O(n)O(n)O(n)，每个元素最多被左右指针各遍历一次。
• 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。