leetcode#3
2019-05-22 / Luo Jinrong   

题目描述

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

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
  • 方法一（自己写的）
  • 对每个ASCⅡ字符设置两个标记，一个记录该字符有无出现过，一个记录上次出现的位置
  • 步骤如下：
    • 设置一个变量，记录以当前位置为尾的最长无重复字符子串的长度
    • 从字符串第一个位置开始遍历，如果该字符没有出现过，当前最大长度+1，并记录该位置为当前字符上次出现的位置
    • 如果该字符出现过，根据当前最大长度大小更新全局最大长度，将子串长度截取到该字符上一次出现位置的后一位，必须擦除该字符上次出现位置之前出现过的字符，将它们标记为未出现过，因为当前子串起始位置已更改，更新当前最大长度，该字符上次出现位置改为当前位置
    • 遍历完该字符串，返回全局最大长度与当前最大长度的最大值，因为该算法只在出现重复字符才更新全局最大长度，所以遍历到最后一个字符可能没有重复，这样的话最后一段子串的长度就不会更新
  • 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int flag[256],pos[256];//flag表示以当前字符上一个字符为结尾的最大不重复字符串中字符的出现情况，pos表示出现的位置
        memset(flag,0,sizeof(flag));//初始化
        int maxlen=0,nowlen=0;//nowlen为当前字符上一个字符为结尾的最大不重复子串的长度，maxlen为全局最大长度
        for(int i=0;i<s.length();i++){//遍历一遍
            //cout<<"now is pos: "<<i<<endl;
            if(flag[s[i]]){
                //cout<<"找到重复"<<endl;
                if(nowlen>maxlen){
                    maxlen=nowlen;
                }
                for(int j=i-nowlen;j<pos[s[i]];j++){//遍历擦除标记
                    flag[s[j]]=0;
                }
                nowlen=i-pos[s[i]];
                //cout<<"当前长度置为: "<<nowlen<<endl;
                pos[s[i]]=i;
            }
            else{
                //cout<<"未找到重复"<<endl;
                nowlen++;
                flag[s[i]]=1;
                pos[s[i]]=i;
            }
        }
        return maxlen>nowlen?maxlen:nowlen;//复杂度O(n)
    }
};
  • 方法二（看题解的，但是思想跟我自己想的差不多，只不过这个写起来比较简单）
  • 滑动窗口
  • 对每个ASCⅡ字符一个标记，记录该字符有无出现过
  • 步骤如下：
    • 定义一个队列，从头遍历字符串
    • 如果当前字符没有出现过，则入队，此时当前最大长度即为队列中的元素个数
    • 如果出现过，更新全局最大长度，再逐个出队，知道弹出与当前字符重复的字符为止
    • 返回全局最大长度与队列大小的最大值，理由同上
  • 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxlen=0,flag[256];
        queue<char> q;
        char tmp;
        memset(flag,0,sizeof(flag));
        for(int i=0;i<s.length();i++){
            if(flag[s[i]]&&q.size()>maxlen){//当重复时更新全局最大值
                maxlen=q.size();
            }
            while(flag[s[i]]){//出队直到不存在重复元素
                tmp=q.front();
                flag[tmp]=0;//擦除标记
                q.pop();
            }
            q.push(s[i]);//当前元素入队
            flag[s[i]]=1;
        }
        return maxlen>q.size()?maxlen:q.size();
    }
};

return 0;

本文链接：
https://luojinrong.github.io/2019/05/22/leetcode-3/