LeetCode 3 無(wú)重復(fù)字符的最長(zhǎng)子串

題目描述

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。

示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

示例 3:

輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。 請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

題解一

直接雙指針掃描，掃描是 O(n)的，但是還得判斷區(qū)間i到j(luò)有沒(méi)有重復(fù)的 O(n)?？偟木褪瞧椒降?/p>

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int res = 0;
        int len = s.size();
        int j = 0;
        for(int i = 0;i < len; i++){
           while(j < len && check(s,i,j))   j++;

           res = max(res,j - i);
        }
        return res;
    }

    bool check(string s,int i,int j){
        
        for(int x = i;x<j;x++)
            if(s[x] == s[j])
                return false;
        return true;
    }
};

題解二

優(yōu)化題解一，把判斷區(qū)間i到j(luò)有沒(méi)有重復(fù)的 O(n)的算法變?yōu)镺(1),

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int res = 0;
        int j = 0;
        int len = s.size();
        for(int i = 0;i < len;i++){

            while(hash[s[j]] <  1 && j < len)  hash[s[j++]] ++;
            res = max(j - i,res);
            hash[s[i]] --;
        }

        return res;
    }
};