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

小鱼儿 2021-09-16 16:48 317阅读 0赞

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

*  给定一个字符串，找出不含有重复字符的最长子串的长度。
 *   示例 1:
    
        输入: "abcabcbb"
          		输出: 3 
          		解释: 无重复字符的最长子串是 "abc"，其长度为 3。
 *   示例 2:
    
        输入: "bbbbb"
          		输出: 1
          		解释: 无重复字符的最长子串是 "b"，其长度为 1。
 *   示例 3:
    
        输入: "pwwkew"
          		输出: 3
          		解释: 无重复字符的最长子串是 "wke"，其长度为 3。
          		请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
 *  解法1：暴力法（该方法在面对长度很长的数据时，不能通过OJ)  
    设有两个指针 i、j , i 指向字符串的第一个字符，j 指向 i 之后的字符，如果j指向的字符出现在临时字符串中 则 判断临时字符串的长度，并且 i 进行迭代， j 重新指向 i之后的字符。代码如下：

public int lengthOfLongestSubstring(String s) {
            String str = null;
            int max = 0;
            for (int i = 0;i < s.length();i++){
                str = s.charAt(i)+"";
                for(int j = i + 1;j < s.length();j++){
                    if(str.contains(s.charAt(j)+""))
                        break;
                    str+=s.charAt(j);
                }
                if(str.length()>max)
                    max = str.length();
            }
            return max;
        }

*  解法2：优化暴力法  
    因为在上面的代码中我们每次都将新的字符添加到临时数组，但是由于字符串是不可变的，我们每次都将大量无用的临时字符串存储起来，这回造成字符串常量池溢出，所以我们应该避免保存不断保存字符串。此时可以使用数组或集合保存字符，代码如下：

public int lengthOfLongestSubstring(String s) {
    	public int lengthOfLongestSubstring(String s) {
            List<Character> list = new ArrayList<Character>();
            if (s.length() == 0)
                return 0;
            int max = 0;
           for (int i = 0;i < s.length();i++)
           {
               list.add(s.charAt(i));
               for (int j = i+1;j < s.length();j++)
               {
                   if(list.contains(s.charAt(j)))
                        break;
                    list.add(s.charAt(j));
               }
               if(list.size() > max) {
                   max = list.size();
               }
               list.clear();
           }
           return max;
        }

*  解法三：滑动窗口  
    在KMP算法中，我们学习过滑动窗口，就是避免i每次都要不断的回溯，例如有如下字符串：  
    ![在这里插入图片描述][70]  
    在我们完成第一次判断时，i,j指向如下：  
    ![在这里插入图片描述][70 1]  
    接着我们需要进行第二次判断时，i，j指向如下：  
    ![在这里插入图片描述][70 2]  
    第四次判断时，i,j指向如下：  
    ![在这里插入图片描述][70 3]  
    注意，第二、三、四次判断时，这些都是没有必要的，因为我们之前已经得到了有序字符串，我们只需在第一次判断后，将 i 直接移向如下图所示：  
    ![在这里插入图片描述][70 4]  
    这样可以避免大量没有意义的移动。  
    代码如下：

List<Character> list = new ArrayList<Character>();
            if (s.length() == 0)
                return 0;
            int max = 0;
            for (int i = 0;i < s.length();i++)
            {
                list.add(s.charAt(i));
                int temp = 0;
                for (int j = i+1;j < s.length();j++)
                {
                    if(list.contains(s.charAt(j))) {
                    
                        i = s.indexOf(s.charAt(j),i);	//在这里我们避免i回溯
                        
                        break;
                    }
                    list.add(s.charAt(j));
                }
                if(list.size() > max) {
                    max = list.size();
                }
                list.clear();
            }
            return max;

本次分析到此，如有不足，多多指教。

[70]: /images/20210813/8b3bb261ea31465a92cebe80c2593b6b.png
[70 1]: /images/20210813/197b9c63a6bd4c75869e0616773f3659.png
[70 2]: /images/20210813/d9a8ae3c60634f4b93fea67294993495.png
[70 3]: /images/20210813/0f7acc0da6874d4e9935bf0fe8e33572.png
[70 4]: /images/20210813/b666ed0c93fc4f7788d150ecb49c0af3.png