LeetCode刷题之旅（3）--无重复字符的最长子串（中等题）

没有简单的题目，或者说，再简单的题目，只要追求极致，都会要花心思。好好加油吧<->

题目:无重复字符的最长子串

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

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

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

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

解题思路：

方法1：

首先，因为键盘可输入字符为128个，所以先int一个128的数组并且初始化为0，用此数组来记录是否重复，然后在循环中判断，如果为0，那么就累加长度，并且记录最大长度。然后在不为0的时候，再初始化数组为0。很明显，这个初始化很耗时，所以又想了下面的方法。

方法2：

双游标，i,j两者之差j-i+1就是子串的长度，然后数组记录的不再是字符是否重复了，而是记录最后一个字母在s串中的位置。细节在于，i在字母重复的时候，会变成字母所在的位置，判断的时候的细节在于，重复的字母的位置如果在i的左边，则表示不会在i到j的子串中重复。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int arr[128]={0};
        int max_length=0,i,j;
        for(i=0,j=0;j<s.size();++j)
        {
            if(arr[(int)s[j]]==0||arr[(int)s[j]]-1<i)
            {
                arr[(int)s[j]]=j+1;//保持字符 s[j] 在s中的位置+1 比如0位 ，最后保存的是1
                //length++;
                if(j-i+1>max_length)
                {
                    max_length=j-i+1;
                }
               
            }
            else
            {
                if(arr[(int)s[j]]-1<i)
                {
                    
                }
                else
                {
                    i=arr[(int)s[j]];
                    arr[(int)s[j]]=j+1;
                    /*if(j-i>max_length)
                    {
                        max_length=j-i+1;
                    }*/
                }
               
                
            }
        }
        
        return max_length;
        
        
    }
};
static const auto _____ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
执行用时：12 ms