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

阳光穿透心脏的1/2处 2022-05-26 11:24 136阅读 0赞

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

[题目描述][Link 1]

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：

给定 `"abcabcbb"` ，没有重复字符的最长子串是 `"abc"` ，那么长度就是3。

给定 `"bbbbb"` ，最长的子串就是 `"b"` ，长度是1。

给定 `"pwwkew"` ，最长子串是 `"wke"` ，长度是3。请注意答案必须是一个子串，`"pwke"` 是 *子序列* 而不是子串。

*  [Longest Substring with At Most Two Distinct Characters][]

--------------------

#include<bits/stdc++.h>
    using namespace std;
    /********************提交代码********************/
    int lengthOfLongestSubstring(char* s)
    {
        int i,j,n=strlen(s),res=0,ans=0;
        int *a=(int*)malloc(n*sizeof(int));
        for(i=0; i<n; ++i)
        {
            a[i]=s[i]-'A';//字符数组转成int存储方便判断是否vis
            if(a[i]>res)//转换的最大数值
                res=a[i];
        }
        bool *vis=(bool*)malloc((res+1)*sizeof(bool));//访问标记
        for(j=0; j<n; ++j)
        {
            res=0;
            for(i=0; i<n; ++i)//注意初始化
                vis[a[i]]=false;
            for(i=j; i<n; ++i)//从第i个位置依次往后遍历
            {
                if(!vis[a[i]])//未出现过
                {
                    vis[a[i]]=true;
                    ++res;
                }
                else//出现过直接跳出
                    break;
                if(res>ans)//更新最长串长度
                    ans=res;
            }
        }
        return ans;
    }
    /***************************************************/
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        char s[1000];
        while(cin>>s)
        {
            cout<<lengthOfLongestSubstring(s)<<endl;
        }
        return 0;
    }

暴力出奇迹(￣▽￣)~\*，从头到尾依次作为起始位置遍历到最后（有重复字符）。

三点。

1、不能用a=int(c)这样的显式强制转换，我只能隐式强制转换了；

2、申请vis的内存时注意取最大值加一。

3、子序列可以不是连续字符，而子串必须是连续的。

[Link 1]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/
[Longest Substring with At Most Two Distinct Characters]: https://leetcode-cn.com/problems/longest-substring-with-at-most-two-distinct-characters