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

既然是子串…我第一个想到的就是简单尺取法了…过一遍O(n)的性能…简单写了写也就ac了

过了以后发现这种经典问题有更简单的思路…当看到重复的时候其实以及可以知道到重复位置以前的最长长度已知…可以直接跳到重复字符的下一位置…

我的代码如下

++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start=0,end=0,maxans=0,tmpans=0;
        bool check[256];
        memset(check,0,sizeof(check));
        while(end<s.length())
        {
            if(check[s[end]])
            {
                check[s[start]]=false;
                ++start;
                --tmpans;
            }
            else
            {
                check[s[end]]=true;
                ++end;
                ++tmpans;
                maxans=max(maxans,tmpans);
            }
        }
        return maxans;
    }
};