LeetCode3—Longest Substring Without Repeating Characters

刺骨的言语ヽ痛彻心扉 2022-06-09 07:38 148阅读 0赞

本类型博客中的各算法的时间复杂度分析均为博主自己推算，本类型博客也是博主自己刷LeetCode的自己的一些总结，因此个中错误可能较多，非常欢迎各位大神在博客下方评论，请不吝赐教

#     #

# 一、问题 #

*  输入：一个字符串S
 *  输出：输出它的最长子串，该子串中不能包含相同的字符
 *  假设条件：字符串中的字符全部时ASCII吗，即编码值在0-128之间

# 二、输入输出示例 #

*  输入：“abcaa”
 *  输出：3，因为最长子串为"abc"

# 三、解法 #

最大不重复子串肯定包含在两个重复的字符之间，或者是某个字符跟开头或结尾之间的子串为最大不重复子串。因此在遍历时凡是第一次遇到重复的字符，其之间的子串必定是不重复的，此时判断该子串的长度，并与已经存在的最大长度作比较，然后新的子串必定位于重复的两个字符的左侧那个字符的右边，然后在右边继续使用之前的方法寻找子串即可。对于字符串的遍历为n，另一个部分则是在已经遍历的字符中的搜索当前字符，整体算法的时间复杂度为n\*搜索算法的时间复杂度。

## 解法一：使用散列思想存储已经遍历的字符 ##

**解题思路**：由于本题中的字符均为ASCII字符，因此最多有128种字符，创建一个长度为128的数组，每个位置存储该字符最近一次出现的索引，这样查找的时间复杂度为O(1)

package com.happy.leetcode.p3;
    
    
    public class LongestSubstringWithoutRepeatingCharactersV1 {
    
    
        public static void main(String[] args) {
            String s = "au";
            System.out.println(s);
            System.out.println(new LongestSubstringWithoutRepeatingCharactersV1().lengthOfLongestSubstring(s));
        }
    
    
        public int lengthOfLongestSubstring(String s) {
            if ("".equals(s.trim())) {
                return 0;
            }
            int[] characters = new int[128];
            int maxLength = 1;
            int currentLength = 0;
            int currentPos = -1;
            for (int i = 0; i < s.length(); i++) {
                int index = (int) s.charAt(i);
                if (characters[index] > 0 && characters[index]>currentPos) {
                    currentLength = i - 1 - currentPos;
                    currentPos = characters[index] - 1;
    
    
                    if (maxLength < currentLength) {
                        maxLength = currentLength;
                    }
                }
                characters[index] = i + 1;
            }
            currentLength = s.length() - 1 - currentPos;
            if (maxLength < currentLength) {
                maxLength = currentLength;
            }
            return maxLength;
        }
    
    
    }

**时间复杂度分析**：n\*1，时间复杂度为 **O(n)**

**【注】**该算法不是通用算法，由于散列算法的限制，因此该算法仅仅针对ASCII码字符

## 解法二：搜索采用Java的indexOf函数 ##

**解题思路**：搜索时可以采用Java自带的indexOf函数，其实此函数实际为遍历一遍各个字符，找到想等的就返回索引

package com.happy.leetcode.p3;
    
    
    public class LongestSubstringWithoutRepeatingCharactersV2 {
    
    
        public static void main(String[] args) {
            String s = "cddba";
            System.out.println(s);
            System.out.println(new LongestSubstringWithoutRepeatingCharactersV2().lengthOfLongestSubstring(s));
        }
    
    
        public int lengthOfLongestSubstring(String s) {
            if ("".equals(s.trim())) {
                return 0;
            }
            int maxLength = 1;
            int currentLength = 0;
            int currentPos = 0;
            for (int i = 0; i < s.length(); i++) {
                int index = s.indexOf(s.charAt(i), currentPos);
                if (index >= 0 && index < i) {
                    currentLength = i - currentPos;
                    currentPos = index + 1;
    
    
                    if (maxLength < currentLength) {
                        maxLength = currentLength;
                    }
                }
            }
            currentLength = s.length() - currentPos;
            if (maxLength < currentLength) {
                maxLength = currentLength;
            }
            return maxLength;
        }
    
    
    }

**时间复杂度分析**：indexOf的时间复杂度为n，因此总的时间复杂度为 **O(n^2)**

##        ##