目录
基本概念
209.长度最小的子数组
一、题目描述
二、思路解析
三、代码
3.无重复字符的最长子串
一、题目描述
二、思路解析
三、代码
1004.最大连续1的个数
一、题目描述
二、思路解析
三、代码
1658.将x减到0的最小操作数
一、题目描述
二、思路解析
三、代码
基本概念
若问题分析的对象是[一段连续的区间]，我们就可以考虑使用[滑动窗口]解决问题。
滑动窗口其实就是两个同向的指针，不停地有数据进入这两个指针的区间，也不停地有数据要退出这个区间，这个区间在整个数组中来回滑动，故名[滑动窗口]。
209.长度最小的子数组
一、题目描述
OJ题目链接：力扣（LeetCode）
二、思路解析
三、代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums)
{
int left = 0;
int right = left;
int min_len = nums.size();//长度最小的连续子数组的长度
int sum = 0;
while(right < nums.size())
{
sum += nums[right];
while(sum >= target)
{
int len = right - left + 1;//左右区间长度
min_len = min(min_len, len);//实时更新
sum -= nums[left];
left++;
}
right++;
}
if(right - left == nums.size())//当所以sum均不满足target时
{
return 0;
}
else
return min_len;
}
};3.无重复字符的最长子串
一、题目描述
OJ题目链接：力扣（LeetCode）
二、思路解析
三、代码
//暴力法比对元素
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int left = 0;
int right = 0;
int max_len = 0;
while(right < s.size())
{
int tmp = left;
while(tmp < right)
{
if(s[tmp] == s[right])
break;
tmp++;//1.如果提前退出，那么tmp != right
//2.tmp可以记录区间中与s[r]相同元素的位置
}
if(tmp == right)//如果区间中没有相同元素，后侧元素入窗口
right++;
else//如果区间中有相同元素，出窗口——直接修改left的值
left = tmp + 1;
max_len = max(max_len, right - left);
}
return max_len;
}
};//哈希表记录法
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int hash[128] = {0};
int left = 0, right = 0, max_len = 0;
while(right < s.size())
{
hash[s[right]]++;//进窗口
while(hash[s[right]] > 1)//判断
{
hash[s[left]]--;//出窗口
left++;
}
max_len = max(max_len, right - left + 1);//更新
right++;
}
return max_len;
}
};1004.最大连续1的个数
一、题目描述
即找有最长1的区间，该区间0的个数不超过k个。
OJ题目链接：力扣（LeetCode）
二、思路解析
三、代码
class Solution {
public:
int longestOnes(vector<int>& nums, int k)
{
int cnt = 0, max_len = 0;
for(int left = 0, right = 0; right < nums.size(); right++)
{
if(nums[right] == 0) cnt++;//进窗口
while(cnt > k) //判断
{
if(nums[left] == 0) cnt--;//出窗口
left++;
}
max_len = max(max_len, right - left + 1);//更新
}
return max_len;
}
};1658.将x减到0的最小操作数
一、题目描述
OJ题目链接：力扣（LeetCode）
二、思路解析
这道题目我们可以换个角度理解：
这样一看，我们的题目就变成了在数组中找到和为 sum - x 的最长连续子数组！
三、代码
class Solution {
public:
int minOperations(vector<int>& nums, int x)
{
int left = 0, right = 0, remainder_n = INT_MAX, sum = 0, n = nums.size();
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];//计算数组所有元素之和
}
int remainder = sum - x;//计算剩余元素之和
if(remainder < 0) return -1;//特殊情况判断
int tmp_sum = 0;
for(; right < nums.size(); right++)
{
tmp_sum += nums[right];//进窗口
while(tmp_sum > remainder) //判断
{
tmp_sum -= nums[left];//出窗口
left++;
}
if(tmp_sum == remainder)//更新结果
remainder_n = min(remainder_n, n - (right - left + 1));
}
return remainder_n == INT_MAX ? -1 : remainder_n;
}
};
