滑动窗口

发表于： 分类于：
字数： 147 阅读：≈ 1分钟 浏览：
  • leetcode一道题，无重复字符的最长子串
  • 滑动窗口原理好理解，脑子中要抽象出滑动窗口那个图才行
  • 同时还用了哈希表来帮助判断有无重复元素
class Solution {
public:
    //动态规划，从左往右遍历
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int n = s.size();
        int rk=-1,ans=0;
        for(int i=0;i<n;i++){
            //左指针右移
            if(i!=0){
                occ.erase(s[i-1]);
            }
            //通过哈希集合occ.count来判断是否有重复字符
            while(rk+1<n && !occ.count(s[rk+1])){
                occ.insert(s[rk+1]);
                rk++;
            }
            ans=max(ans,rk-i+1);
        }
        return ans;
    }
};