LeetCode笔记-0003-无重复字符的最长子串

题目信息

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目解答

读题可知，我们要从一个字符串中找到最长的不重复的子串。

解法一：暴力解法

首先暴力解决，定义两个变量i、j，i指向子串开头，j指向子串结尾，定义一个函数，用来判断从i到j是否存在重复的字符，代码如下：

/**
* 暴力解法
* for循环，对每个子字符串都进行比较，取最大的长度
* 时间复杂度：O(n^3)
* 空间复杂度：
* 缺点：大量的重复比较
*
* @param s
* @return
*/
public static int lengthOfLongestSubstringByViolence(String s) {
    int sLength = s.length();
    int maxLengthOfLongestSubstring = 0;// 最大长度
    for (int i = 0; i < sLength; i++)
        for (int j = i + 1; j <= sLength; j++)
            if (allUnique(s, i, j))
                maxLengthOfLongestSubstring = Math.max(maxLengthOfLongestSubstring, j - i);
    return maxLengthOfLongestSubstring;
}

private static boolean allUnique(String s, int start, int end) {
    Set<Character> set = new HashSet<>();
    for (int i = start; i < end; i++) {
        char ch = s.charAt(i);
        if (set.contains(ch))
            return false;
        set.add(ch);
    }
    return true;
}

暴力解决的代码逻辑上是可以实现的，不过效率很慢，进行了很多次的无效判断，放到LeeCode中执行会提示超时：

暴力解法在LeeCode超时

解法二：滑动窗口

采用滑动窗口的形式进行解答，我们仍然定义两个变量i、j，i指向子串开头，j指向子串结尾，假设从i到j-1的子串S_ij不存在重复字符，那我们只需要检验S[j]是不是已经存在于子串S_ij中即可，若S[j]存在于S_ij子串中，i 向右滑动，若S[j]不存在于S_ij子串中，j 向右滑动，并计算最大长度。代码如下：

/**
* 滑动窗口，以[i,j)为窗口，向右比较窗口是否含有重复值，
* 若有重复值，则向右移一位（i++）；
* 否则扩大窗口，j向右移一位（j++）；
*
* @param s
* @return
*/
public static int lengthOfLongestSubstringBySlidingWindow(String s) {
    int sLength = s.length();
    int maxLengthOfLongestSubstring = 0, i = 0, j = 0;// 最大长度
    Set<Character> set = new HashSet<>();
    while (i < sLength && j < sLength) {
        if (set.contains(s.charAt(j)))
            //若S[j]存在于S<sub>ij</sub>子串中，i 向右滑动
            set.remove(s.charAt(i++));
        else {
            //若S[j]不存在于S<sub>ij</sub>子串中，j 向右滑动，并计算最大长度
            set.add(s.charAt(j++));
            maxLengthOfLongestSubstring = Math.max(maxLengthOfLongestSubstring, j - i);
        }
    }
    return maxLengthOfLongestSubstring;
}

解法三：优化滑动窗口

在上面的滑动窗口中，我们发现每次存在重复数据时，i向右移一位，但假设字符串为qwertwertyuio，S_ij子串为qwert，j继续像右移动，S[j]="w"，此时重复需要将i向右移动两位，在解法二中需要进行两次循环才能够将i向右移动两位，我们可以对此进行优化，将i直接移动到准确的位置，代码如下：

/**
*在滑动窗口的设计中，
*如果有重复的数据，每次只向右移一位，假设重复数据在第三位，就需要右移三次，浪费效率，
*可直接将i移动到重复数据之后的位置
*
*@params
*@return
*/
public static int lengthOfLongestSubstringByOptimizeSlidingWindow(String s){
    int sLength = s.length();
    int maxLengthOfLongestSubstring = 0;// 最大长度
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0, j = 0; j < sLength; j++) {
        if (map.containsKey(s.charAt(j)))
            // 确保i不会回退，例如:abba，如果i不取最大值，j=3时，i会读到1，结果为3就错了
            i = Math.max(map.get(s.charAt(j)), i);
        maxLengthOfLongestSubstring = Math.max(maxLengthOfLongestSubstring, j - i + 1);
        map.put(s.charAt(j), j + 1);
    }
    return maxLengthOfLongestSubstring;
}