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

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

题解

将字符串转化为字符数组，利用 HashSet 去除重复字符的功能，从第一个字符开始，放入 HashSet 中，直到出现重复的字符为止，此时就是从第一个字母开始的最大子串长度；然后第二次从第二个字符开始，进行第一步的操作，求出从第二个字符开始的最大子串长度。利用外层 for 循环控制从每一个个字符开始的子串的长度，内层 for 循环比较是否是连续的非重复字符串。

注意事项

• 相当于一个变相的双层 for 循环，寻找最长子串的长度，外层 for 循环控制着从每一个字符开始

复杂度分析

• 时间复杂度：
• 空间复杂度：

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 字符最大长度
        int maxLength = 0;
        if(s == null){
            return maxLength;
        }
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            Set<Character> subSet = new HashSet<Character>();
            // 从第 i 个元素开始的，子串的最大长度
            int subLength = 0;
            for(int k = i; k < chars.length; k++){
                if(!subSet.contains(chars[k])){
                    subSet.add(chars[k]);
                } else{
                    // 包含重复字符串，跳出从这个字符串开始的子串
                    break;
                }
                subLength = subSet.size();      
            }
            // 分别对比从每个字符串开始的，最大子串的长度，如果长与上一个子串的最大长度，进行替换
            if(maxLength < subLength){
                maxLength = subLength;
            }
        }
        return maxLength;
    }
}

题解2

滑动窗口：定义一个左侧指针，定义一个右侧指针，右侧指针一直向右移动，直到出现重复元素位置；
然后左侧指针开始启动，左侧指针向右移动一个位置，我们从 HashSet 中移除一个重复的字符，在右侧指针向右移动时，我们向 HashSet 中添加一个字符。

注意事项

• i + 1左侧字符右进一位，一定要先移除 HashSet 中的字符数组的第一个元素，代表着一个新的子串的产生

复杂度分析

• 时间复杂度：,为左侧指针和右侧指针进行字符串进行遍历。
• 空间复杂度：

代码

public int lengthOfLongestSubstring(String s) {

        // 方法二：滑动窗口
        int subLength = 0;
        int length = s.length();
        int rightPoint = -1;
        Set<Character> subSet = new HashSet<Character>();
        for(int i = 0; i < length; i++){
            if(i != 0){
                subSet.remove(s.charAt(i - 1));     
            }
            while(rightPoint + 1 < length && !subSet.contains(s.charAt(rightPoint + 1))){
                subSet.add(s.charAt(rightPoint + 1));
                rightPoint++;
            }
            subLength = Math.max(subLength,rightPoint - i + 1);
        
        }
        return subLength;

    }