通过 双指针的 同向移动
算法应用的场景：
满足xxx条件（计算结果，出现次数，同时包含）
最长/最短
子串 /子数组/子序列
例如：长度最小的子数组
滑动窗口 使用思路 （寻找最长）
–核心：左右指针（l,r）在起始点，r 向右逐位滑动循环
每次滑动过程中
如果 ：窗内元素满足条件，r向右扩大窗口。并更新最优结果。
如果：窗内元素不满足条件，l向右缩小窗口
–r到达结尾
滑动窗口（寻找最短）
-核心：左右 双指针（l,r）在起始点，R向右逐位滑动循环
每次滑动过程中
如果：窗内元素满足条件 ，L向右缩小窗口
如果：窗内元素不满足条件，R向右扩大窗口
r到达结尾。
//最长模板
初始化 l,r,re,ans
while(右指针没有到结尾)
{
窗口扩大，加入right指针对应的元素，更新当前的re
while(re不满足要求)
{
窗口缩小，移出l对应的元素，l右移
}
更新最优结果 ans
r++;
}
最短模板
初始化 l,r,re,ans
while(右指针没有到结尾){
窗口扩大，加入r对应的元素，更新当前的result
while(result满足条件)
{
更新最优结果ans
窗口缩小，移出l对应的元素，l右移
}
r++;
}
click me!
n target
找出 数组中 满足其和大于等于 target的长度最小的子数组
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l=0,r=0;
int cursum=0;int ans=0;
while(r<nums.size())
{
cursum+=nums[r];
while(cursum>=target){
if (r-l+1<ans||ans==0)
ans=r-l+1;
cursum-=nums[l];
l++;
}
r++;
}
return ans;
}
};
click me
给你一个字符串s ，找出其中不含有重复字符的最长子串的长度。
上一题中我们 使用 curcum来维护区间的和。
在这一题中，我们要有 能判断区间是否有重复元素的东西。使用map<int,int>
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char,int>mp;
int l=0,r=0;int ans=0;
//找最长的
while(r<s.size())
{
mp[s[r]]++;
while (mp[s[r]]>1){
mp[s[l]]--;
l++;
}
ans=max(ans,r-l+1);
r++;
}
return ans;
}
};
添加链接描述
整数数组 nums 整数k
返回子数组内 所有元素的乘积 严格小于k的个数。
对于一个符合条件的子数组，以r结尾的 小的子数组 有长度为1,2，一直到 r-l+1的长度。
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n = nums.size(), ret = 0;
int prod = 1, i = 0;
for (int j = 0; j < n; j++) {
prod *= nums[j];
while (i <= j && prod >= k) {
prod /= nums[i];
i++;
}
ret += j - i + 1;
}
return ret;
}
};
作者：力扣官方题解
链接：https://leetcode.cn/problems/subarray-product-less-than-k/solutions/1463527/cheng-ji-xiao-yu-k-de-zi-shu-zu-by-leetc-92wl/
来源：力扣（LeetCode）
添加链接描述
题目可以转化成 求子数组 和为 sum-x 的最长度。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum=0;bool flag=0;
for (auto i:nums )sum+=i;
int tar=sum-x;
if(tar<0)return -1;
else if (tar==0) return nums.size();
//找小于等于最长的子数组
int n=nums.size();int i=0;int ans=0;int cursum=0;
for (int j=0;j<n;j++)
{
cursum+=nums[j];
while(cursum>tar){
cursum-=nums[i];
i++;
}
这里略有不同，只有子数组的和为tar的时候，才更新答案
if (i<=j&&cursum==tar)
{ans=max(ans,j-i+1);
flag=1;
}
}
if(flag) return n-ans;
else return -1;
}
};
添加链接描述
这道题 主要 想说的是，时间复杂度的计算。
m是s的长度，n是t的长度
我一开始 认为 是 n*m.在每一次移动指针的时候，都要判断 我们选出来的区间是否还符合条件，我意识 认为 ，每次判断是o(n)，也就是遍历一遍t数组的时间复杂度。
数据是1e5，我一想妥妥超时。
但实际上，我们判断的时间复杂是 t数组中，O(符号的种类),所以最多也就是128
class Solution {
bool is_(int cnt_s[],int cnt_t[])
{
for (int i='A';i<='Z';i++)
{
if (cnt_s[i]<cnt_t[i])
return false;
}
for (int i='a';i<='z';i++)
{
if (cnt_s[i]<cnt_t[i])
return false;
}
return true;
}
public:
string minWindow(string s, string t) {
int cnt_s[128],cnt_t[128];
for (char c:t)cnt_t[c]++;
int len=s.length();
int j=0,i=0;int el=0,er=s.size()-1;
bool flag=0;
for (j=0;j<len;j++)
{
cnt_s[s[j]]++;
while(i<=j&&is_(cnt_s,cnt_t))
{
if (j-i<er-el){
er=j;el=i;
}
flag=1;
cnt_s[s[i]]--;
i++;
}
}
string tt;
if (flag){
for (int k=el;k<=er;k++)
{
cout<<s[k]<<" ";
tt+=s[k];
}
}
return tt;
}
};
滑动窗口先整这些吧，基本的思路有了。等碰到题，不会的时候，在想吧