滑动窗口---长度最小的子数组、无重复字符的最长子串、最大连续1的个数 III、将 x 减到 0 的最小操作数
一.209. 长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 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
解题思路
可以暴力求解，列举出所有总和大于等于target的子数组，找到长度最小的子数组，返回长度就行。但是时间复杂度太大，我们可以尝试用滑动窗口来写。
滑动窗口：“滑动窗口”是一种动态视窗的数据处理技术，通过维护一个固定或可变大小的窗口，在数据流或序列上执行局部操作，将全局问题转化为局部子问题，从而显著降低时间复杂度。在算法领域，它常用于字符串、数组的连续区间计算；在网络通信中，TCP滑动窗口是流量控制与拥塞控制的核心机制。
滑动窗口实质上就是通过双指针(left/right)扩展或收缩。右指针向右滑动，以扩展窗口；左指针向右滑动，以收缩窗口。
本题是应用滑动指针，右指针不断右移，直到窗口内的值大于target，左指针右移动，保证窗口尽可能小，实时记录窗口长度，直到找到最小的子数组
代码实现
int minSubArrayLen(int target, int* nums, int numsSize) {
//滑动指针
//1.定义左右双指针
int left = 0;
int minLen = numsSize + 1;//初始值尽可能大
int sum = 0;
//2.右指针遍历
for(int right = 0; right < numsSize; right++)
{
sum += nums[right];
//3.如果和大于等于target,左指针移动
while(sum >= target)
{
//4.记录当前长度，与最小长度作比较
int currentLen = right - left + 1;
if(currentLen < minLen)
{
minLen = currentLen;
}
sum -= nums[left];
left++;
}
}
if(minLen == numsSize + 1)
{
return 0;
}
return minLen;
}总结
滑动窗口，右指针遍历数组，扩窗口；左指针保证窗口尽可能小，缩窗口。
二.无重复字符的最长子串
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
解题思路
一般思路是暴力求解，找出所有无重复字符子串，再比较子串长度，得出答案。进阶思路就是用滑动窗口，右指针遍历数组，一旦碰到已经出现的字符，左指针右移到已出现的字符处，以此使得窗口尽可能大，即可找到最长子串。
需要：实时记录字符上一次出现的位置，保证可以清晰知道这个字符是否出现过
字符串类型的题会用到string，要注意用字符串类型进行求解，不过本题要求的是返回最长子串长度
代码实现
int lengthOfLongestSubstring(char* s) {
//1.定义左指针，最大值，实时记录字符上一次出现位置的数组
int left = 0;
int maxLen = 0;//初始值要尽可能小
int len = strlen(s);
int last[128] = {0};//用于记录字符上一次出现的位置
//2.定义右指针遍历数组，扩展窗口
for(int right = 0;right < len;right++)
{
unsigned char c = s[right];//把 char 强制转换成 0~255 的无符号值，确保下标永远是非负数
//3.当前字符出现过，左指针移动
if(last[c] > left)
{
left = last[c];
}
//更新记录字符出现的位置
last[c] = right + 1;
//4.计算当前长度与已存最大长度做比较
int currentLen = right - left + 1;
if(currentLen > maxLen)
{
maxLen = currentLen;
}
}
return maxLen;
}总结
滑动窗口，实时记录已出现字符，保证滑动窗口尽可能大
三.1004. 最大连续1的个数 III
题目描述
给定一个二进制数组 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，使得不连续的1连续起来，并连续1个数最大，正面想很难，直到我给它画了一个窗口。
我们发现此时是满足题意的，窗口内有两个零，可以换成1，相当于窗口有5个1，那求最长1的个数其实不就是让这个窗口尽可能大，零的个数小于等于k即可
如果零的个数大于k了怎么办？移动左指针，直到零的个数<=K。
保证滑动窗口最大，即可找到最大1的个数
代码实现
int longestOnes(int* nums, int numsSize, int k) {
//滑动窗口，让窗口内的零个数
//定义左右指针
int left = 0;
int maxLen = 0;
int zeronum = 0;
//滑动窗口，实时记录零的个数，保证窗口的零个数不大于k
for(int right = 0; right < numsSize; right++)
{
if(nums[right] == 0)
{
zeronum++;
}
//如果零的个数大于k，左指针右移，直到零的个数小于k
while(zeronum > k)
{
if(nums[left] == 0)
{
zeronum--;
}
left++;
}
//比较当前长度与最大长度
int currentLen = right - left + 1;
if(currentLen > maxLen)
{
maxLen = currentLen;
}
}
return maxLen;
}总结
滑动窗口，使窗口内零的个数小于等于k，窗口尽可能大
四.1658. 将 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 。
解题思路
乍一看这不就是对撞双指针，但仔细一看又不对，这不是对撞指针，因为会遇到问题：要删除左右元素，当 sum < x 时，你不知道该删左边还是右边。那怎么求解呢，我百思不得其解。直到看到这个方法------正难则反
代码实现
int minOperations(int* nums, int numsSize, int x) {
//正向思考很难，但反向思考很简单
//正向：找到需要移除的元素，左右元素之和等于x
//反向：用所有元素之和减去x，得出target，再在数组里找和等于target的最长子数组，再用总长度减子数组长
//1.求所有元素之和
int sum = 0;
for(int i = 0; i < numsSize; i++)
{
sum += nums[i];
}
//2.用总和减去x得出target
int target = sum - x;
//特殊情况
if(target == 0)
{
return numsSize;
}
if(target < 0)
{
return -1;
}
//3.定义滑动窗口左右指针
int left = 0;
int maxLen = -1;
int currentsum = 0;
//滑动双指针保证窗口尽可能大
for(int right = 0; right < numsSize; right++)
{
currentsum += nums[right];
while(currentsum > target)
{
currentsum -= nums[left];
left++;
}
//如果和等于target
if(currentsum == target)
{
if(right - left + 1 > maxLen)
{
maxLen = right - left + 1;
}
}
}
if(maxLen == -1)
{
return -1;
}
return maxLen;
}总结
正难则反，先算出总和，减去x，得出目标值target，转化为滑动窗口问题
更多推荐
9
0- 0
已为社区贡献4条内容
所有评论(0)