美文网首页
3.无重复字符的最长子串

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

作者: Jerry_589e | 来源:发表于2019-03-21 16:22 被阅读0次

    题目

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

    示例 1:

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

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

    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
    请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
    https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

    解题

    方法一:滑动窗口(逐个)

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            //char[] chars = new char[256];
            int chars[256]={0}; //ASCII表有127个字符 还有个128的副表 因此申请256个空间 用于计数
            int begin = 0;
            int res = 0;
            for(int i = 0;i<s.length();i++){
                while(begin <= i && chars[s.at(i)] > 0){//处理当前添加的字符重复的问题
                    //下面代码是用于逐个往前滑动  去重
                    chars[s.at(begin)]--;
                    begin++;
                }
                chars[s.at(i)]++;//每次不重复子串的长度+1
                res = max(res,i - begin + 1);//记录不重复子串的最长长度
            }
            return res;
        }
    };
    

    注意
    取单个字符操作:

    • C++为 string.at()
    • JAVA为 string.charAt()
    • string也可以视为数组形式 直接取就可以 例如 s="abcd",s[2] = "c"。


      字符集

    方法二

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            unordered_map<char, int> data;
            int begin = 0, result = 0;
            //i代表字串的起始位置,j表示字串的结束位置
            for (int j = 0; j < s.size(); j++) {
                if (data.find(s[j]) != data.end()) {
                    begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
                }
                result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
                data[s[j]] = j + 1;//记录并更新这个字符最近出现的位置 此处相当于存储之前与之重复的元素的下一个位置  
            }
            return result;
        }
    };
    
    
            for (int j = 0; j < s.size(); j++) {
                if (data.find(s[j]) != data.end()) {
                    begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
                }
                result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
                data[s[j]] = j + 1;//记录并更新这个字符最近出现的位置  
            }
    

    不能写为以下这种形式

            for (int j = 0; j < s.size(); j++) {
                if (data.find(s[j]) != data.end()) {
                    begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
                    begin++;
                }
                result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
                data[s[j]] = j ;//记录并更新这个字符最近出现的位置
            }
    
    错误

    这种形式的错误在于,循环有时候会误加,我们本意是取重复元素的下一个作为开始,但是map存储了所有的元素,因此有时即使无效的重复也会进入循环,使begin+1,减少了长度。
    上面例子就是,begin在第二个m处时,当运行到最后一个t,由于之前map有保存key为t,因此会进入循环,使begin++,因此长度变短,因此此时的操作属于误操作。
    所以直接用数据存储下一个位置这种形式比较可靠。

    相关文章

      网友评论

          本文标题:3.无重复字符的最长子串

          本文链接:https://www.haomeiwen.com/subject/fbhqvqtx.html