滑动窗口（同向的双指针）

通过双指针的同向移动
算法应用的场景：
满足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;
    }
};