4

「算法刷题」数组之滑动窗口专项汇总(力扣版)

 1 year ago
source link: https://magicdeveloperdrl.github.io/2022/06/12/%E7%AE%97%E6%B3%95%E5%88%B7%E9%A2%98-%E6%95%B0%E7%BB%84%E4%B9%8B%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E4%B8%93%E9%A1%B9%E6%B1%87%E6%80%BB-%E5%8A%9B%E6%89%A3%E7%89%88.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

​ 本文记录作者刷题过程中与滑动窗口相关的题目。

1、连续子数组

674. 最长连续递增序列(简单难度)

子数组是原数组中连续的元素,中间不可以删除或添加其他元素,每个元素的相对顺序和原数组相同

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int len=nums.size();
        if(len==1) return 1;
        int res=0;// 最长长度
        int left=0;
        int right=1;
        // 滑动窗口[left,right)表示递增区间,负责搜索数组中的所有递增区间
        while(right<len){
            // 如果新元素递增,扩展右边界
            if(nums[right-1]<nums[right]){
                right++;
            }
            // 如果新元素非递增,更新左边界,扩展右边界
            else{
                left=right;
                right++;
            }
            res=max(res,right-left);//不断更新递增区间的最大长度
        }
        return res;
    }
};

剑指 Offer 57 - II. 和为s的连续正数序列(简单难度)

class Solution {
public:
    /*解析:本题是从正整数序列中查找所有和为target的连续子序列
    难点在于每个连续子序列的长度、数量是不确定的。
    这种类型题,特别是元素都是正整数,特别适合滑动窗口算法。
    请注意,左指针和右指针的移动时机
    当区间和>=target,右移左指针;当区间和<target,右移右指针
    进阶:求解区间和的数学技巧:(left+right)*(right-left+1)/2
    */
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        int left=1;//正整数序列的第1个数
        int right=2;//正整数序列的第2个数
        int sum=0;
        vector<int> sub;
        // 滑动窗口[left,right]
        while(left<right){
            // 计算滑动窗口[left,right]的和
            sum=0;
            sub.clear();
            for(int i=left;i<=right;i++){
                sum+=i;
                sub.push_back(i);
            }
            // 如果区间和==target,移动左指针
            if(sum==target) {
                res.push_back(sub);
                left++;
            }
            // 如果区间和<target,右指针右移
            else if(sum<target) right++;
            // 如果区间和>target,左指针右移
            else left++;
        }
        return res;
    }
};

添加数学公式优化后:

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        int left=1;//正整数序列的第1个数
        int right=2;//正整数序列的第2个数
        int sum=0;
        vector<int> sub;
        // 滑动窗口[left,right]
        while(left<right){
            // 计算滑动窗口[left,right]的和
            sum=(left+right)*(right-left+1)/2;
            // 如果区间和==target,移动左指针
            if(sum==target) {
                sub.clear();
                for(int i=left;i<=right;i++){
                    sub.push_back(i);
                }
                res.push_back(sub);
                left++;
            }
            // 如果区间和<target,右指针右移
            else if(sum<target) right++;
            // 如果区间和>target,左指针右移
            else left++;
        }
        return res;
    }
};

209. 长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLength = INT32_MAX; // 求最小值就以整数的较大值初始化
        int curlength = 0;//当前值
        int start=0;//滑动窗口起始位置
        int end=0;//滑动窗口终止位置
        int sum=0;
        //不满足滑动条件时就不断移动终止位置
        for(int end=0;end<nums.size();end++){
            sum+=nums[end];
            //当满足条件时就不断移动起始位置
            while(sum>=target){
                curlength = end-start+1;//计算当前滑动窗口代表的值
                minLength = minLength < curlength ? minLength : curlength;//注意:当前最小不一定就是全局最小
                sum-=nums[start++];//滑动窗口起始位置后移
            }
        }
        return minLength == INT32_MAX ? 0 : minLength;
    }
};

904. 水果成篮

class Solution {
public:
    int totalFruit1(vector<int>& tree) {
        vector<int> count(tree.size());
        int start = 0;//滑动窗口起始位置
        int end =0;//滑动窗口终止位置
        int dif = 0;//水果种类
        for(end = 0; end < tree.size(); end++) {
            if(count[tree[end]] == 0) {
                count[tree[end]]++;//该种类水果数量+1
                dif++;//种类+1
            }

            if(dif > 2) {
                count[tree[start]]--;
                if(count[tree[start]] == 0) {
                    //start++;
                    dif--;
                }
                
                start++;
            }
        }
        return end - start;
    }
    /*这道题目可以理解为求只包含两种元素的最长连续子序列*/
    int totalFruit(vector<int>& tree) {
        int K = 2;
        int end = 0, start = 0, res = 0;
        unordered_map<int, int> dict;
        for (end = 0; end < tree.size(); end++) {
             dict[tree[end]]++;//该种类水果数量增加
             //当不符合滑动窗口条件时
             while(dict.size() > K) 
             {
                 res = max(res,  end - start);
                 dict[tree[start]]--;
                 if(dict[tree[start]] == 0) {
                    dict.erase(tree[start]);
                 }
                 start++;       
             }
        }
        res = max(res,  end - start);
        return res;
    }
};

3. 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> dict;// <字符,频率>
        // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        int right=-1;
        int res=0;
        // 枚举左指针的位置,初始值隐性地表示为 -1
        for(int left=0;left<s.length();++left){
            if(left!=0) dict.erase(s[left-1]);
            // 当右指针下一步没有到达数组右边界且右指针下一步没有重复,不断地移动右指针
            while(right+1<s.length()&&!dict.count(s[right+1])){
                dict[s[right+1]]++;
                right++;
            }
            // 第 left 到 right 个字符是一个最长的无重复字符子串
            res = max(res, right - left + 1);
        }
        return res;
    }
};

567. 字符串的排列

剑指 Offer II 014. 字符串中的变位词

class Solution {
public:
    /*由于排列不会改变字符串中每个字符的个数,
    所以只有当两个字符串每个字符的个数均相等时,
    一个字符串才是另一个字符串的排列。
    记 s1的长度为n,我们可以遍历2中的每个长度为n 的子串,
    判断子串和s1中每个字符的个数是否相等,
    若相等则说明该子串是s1的一个排列*/
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) return false;
        vector<int> cnt1(26), cnt2(26);
        for (int i = 0; i<n; ++i) {
            ++cnt1[s1[i]-'a'];
            ++cnt2[s2[i]-'a'];
        }
        if (cnt1 == cnt2) return true;
        for (int i = n; i < m; ++i) {
            ++cnt2[s2[i]-'a'];
            --cnt2[s2[i -n]-'a'];
            if (cnt1 == cnt2) return true;
        }
        return false;
    }
};

438. 找到字符串中所有字母异位词

class Solution {
public:
    /**时间复杂度O(N),空间复杂度O(1); 技术:滑动窗口+计数索引
    一、计数索引,两个串中的字母只有小写英文字母,用大小为26的数组存放字母频率
    二、滑动窗口[left,right]
    在s中移动一个滑动窗口,如果滑动窗口内的字母频率>=t的字母频率,则滑动窗口符合条件
    移动滑动窗口时,需要时刻维护滑动窗口内的所有字母频率sFreq
    left的移动范围是[0,s_len-t_len],right的移动范围是[-1,s_len-1]
    如何移动滑动窗口呢?默认先移动right,比较winSize和t.size(),判断是否移动left:
    1) 当winSize < t.size()  移动right;// 此时滑动窗口一定不符合要求
    2) 当winSize == t.size() 并且符合要求时: 添加left到结果中,移动left
    3) 当不符合要求时: 移动left*/
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        int s_len=s.length();
        int p_len=p.length();
        if(s_len<p_len) return res;
        // 统计p的字母频率
        vector<int> pFec(26,0);
        for(char c:p) pFec[c-'a']++;
        // 滑动窗口
        int left=0;// 遍历范围为[0,s_len-p_len]
        int right=-1;// 遍历范围为[-1,s_len-1]
        vector<int> winFec(26,0);
        while(left<=s_len-p_len){
            int winSize=right-left+1;
            // 如果滑动窗口尺寸较小,移动right
            if(winSize<p_len){
                right++;
                winFec[s[right]-'a']++;
            }
            // 如果滑动窗口尺寸正好,检查要求,移动left缩小
            else if(winSize==p_len&&check(winFec,pFec)){
                res.push_back(left);  // 符合条件
                winFec[s[left++]-'a']--; // 缩小窗口
            }
            // 如果滑动窗口尺寸较大,移动left缩小
            else winFec[s[left++]-'a']--; // 缩小窗口
        }
        return res;
    }
    bool check(vector<int>& sFec,vector<int>& pFec){
        for(int i=0;i<26;++i) if(sFec[i]!=pFec[i]) return false;
        return true;
    }
};

76. 最小覆盖子串

class Solution {
public:
    /**时间复杂度O(N),空间复杂度O(1); 技术:滑动窗口+计数索引
    一、计数索引
    该题目的两个串中的字母只有大小写英文字母,可以开辟一个大小为64的数组存放字母频率
    通过字母的ASCII码作为数组的索引,开辟空间的大小为26+6+26=58:26个大写字母,26个小写字母,
    还有中间的6个非字母  A~Z[65~90]  非字母[91~96]  a~z[97~122]
    二、滑动窗口[left,right]
    在s中移动一个滑动窗口,如果滑动窗口内的字母频率>=t的字母频率,则滑动窗口符合条件
    移动滑动窗口时,需要时刻维护滑动窗口内的所有字母频率sFreq
    left的移动范围是[0,s_len-t_len],right的移动范围是[-1,s_len-1]
    如何移动滑动窗口呢?默认先移动right,比较winSize和t.size(),判断是否移动left:
    1) 当winSize < t.size()  移动right;// 此时滑动窗口一定不符合要求
    2) 当winSize >= t.size() :
        2.1) 如果滑动窗口符合要求:
            2.1.1)winSize == t.size()时,一定是最小覆盖子串,直接return
            2.1.2) winSize >  t.size()时,保存left和right,尝试移动left
        2.2) 如果滑动窗口不符合要求:
            2.2.1)如果right移动到头,移动left
            2.2.2) 如果right没有移动到头,移动right
    */
    string minWindow(string s, string t) {
        int t_len=t.size();
        int s_len=s.size();
        if (s_len<t_len) return "";
        // 统计t字符串中每个字母的出现频率
        vector<int> tFreq(64,0);// t字母串的所有字母频率
        for (int i=0; i<t_len; i++) tFreq[t[i]-'A']++;
        // 滑动窗口为[left,right],窗口大小是winSize=right-left+1
        int left = 0, right = -1;
        vector<int> winFreq(64,0);// 滑动窗口的所有字母频率
        int edge[2]={-1,s_len+1}; // 保存的最小覆盖子串的左右边界
        while (left <= s_len-t_len) {
            int winSize=right-left+1;
            //窗口较小时,移动right
            if(winSize<t_len) {
                //if (right+1>=s_len) break;// 防止越界 
                right++;//移动右边界
                winFreq[s[right]-'A']++; 
            }
            // 如果符合要求
            else if(check(winFreq,tFreq)){
                // 如果窗口大小==t的长度,一定是最小覆盖子串
                if (winSize == t.size()) return string(s.begin()+left, s.begin()+right+1);
                // 如果窗口大小>t的长度,不一定是最小覆盖子串,可能要保存,移动left
                else {
                    // 如果比上个保存子串小,则更新
                    if (right-left<edge[1]-edge[0]) {
                        edge[0] = left;
                        edge[1] = right;
                    }
                    winFreq[s[left]-'A']--;
                    left++;
                }
            }
            // 如果不符合要求,移动right
            else{
                // 如果right没有越界,移动right
                if (right+1<s_len) {
                    right++;
                    winFreq[s[right]-'A']++;
                }
                // 如果right已经到头,移动left
                else{
                    winFreq[s[left]-'A']--;
                    left++;
                }
            }
        }
        return edge[0] == -1 ? "" : string(s.begin() + edge[0], s.begin() + edge[1] + 1);
    }
    // 检查此时窗口中的字母频率是否和t的频率一致
    bool check(vector<int>& winFreq, vector<int>& tFreq){
        for(int i = 0;i < 64;i++){
            if (winFreq[i]<tFreq[i]) return false;
        }
        return true;
    }
};

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK