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

题目来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

示例 1:

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

示例 2:

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

示例 3:

输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解法

C++代码:

初次试探:

主要思路是滑动窗口,但代码能有需要精简的地方。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int slen = s.length();      //字符串长度
        int len = 1;                //最长子串长度
        int start = 0;              //开始检索位置
        int t = 0;
        if(s == "")                 //判断空串
            return 0;
        for(int i=0;i<slen;i++)
        {
            if(exist(s,start,i,s[i])==-1) //未找到
            {
                t++;
                continue;
            }else{
                if(t > len)
                    len = t;
                start = exist(s,start,i,s[i]) + 1;
                t = i - start + 1;
            }
        }
        if(t>len)
            len = t;
        return len;
        
    }
    int exist(string &s,int start,int end,char target) //返回相等的索引
    {
        for(int i=start;i<end;i++)
        {
            if(target == s[i])
                return i;
        }
        return -1;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了93.04%的用户

内存消耗 :7.1 MB, 在所有 C++ 提交中击败了100.00%的用户


下解法均为滑动窗口解法

解法一:多重循环

// 对初次试探代码进行改进
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start = 0, end = 0, length = 0, result = 0;
        int slen = s.length();
        while(end < slen)
        {
            char t = s[end];
            for(int i = start;i < end;i++)
            {
                if(s[i] == t) //找到重复 更新
                {
                    start = i + 1;
                    length = end - start;
                    break;
                }
            }
            length++;
            end++;
            result = max(result, length);
        }
        return result;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了98.86%的用户

内存消耗 :7 MB, 在所有 C++ 提交中击败了100.00%的用户

复杂度分析:

时间复杂度:O(n^2)

空间复杂度:O(1)


解法二:利用哈希表优化

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start = 0, end = 0, length = 0, result = 0;
        int slen = s.length();
        unordered_map<char, int> hash;
        while(end < slen)
        {
            char t = s[end];
            if(hash.find(t) != hash.end() && hash[t] >= start) //找到重复 更新
            {
                start = hash[t] + 1;
                length = end - start;
            }
            hash[t] = end;
            end++;
            length++;
            result = max(length, result);
        }
        return result;
    }
};

执行用时 :32 ms, 在所有 C++ 提交中击败了53.42%的用户

内存消耗 :8.5 MB, 在所有 C++ 提交中击败了100.00%的用户

复杂度分析:

时间复杂度:O(n)

空间复杂度:O(n)


解法三:利用数组(桶)优化

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start = 0, end = 0, length = 0, result = 0;
        int slen = s.length();
        vector<int> vec(128,-1);
        while(end < slen)
        {
            int t = s[end];
            if(vec[t] >= start) //找到重复
            {
                start = vec[t] + 1;
                length = end - start;
            }
            vec[t] = end;
            end++;
            length++;
            result = max(length, result);
        }
        return result;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了93.06%的用户

内存消耗 :7.7 MB, 在所有 C++ 提交中击败了100.00%的用户

复杂度分析:

时间复杂度:O(n)

空间复杂度:O(n)