LeetCode算法——无重复字符的最长子串(Java解法)

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

示例 1:

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

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

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

分析：题目要求找出无重复长度的最长子字符串，需要判断是否存在重复操作，这里提供两种解题思路。

思路一：利用 StringBuilder 自带的方法 sb.indexOf('a') 判断字符串sb中是否包含字符 a ，如果包含则返回  a 出现的第一个位置，否则返回 -1 。代码思路接近暴力双循环，外层循环比遍历每一个下标，以当前下标为起始点找出无重复字符的最长子串，动态记录每次遍历的最长子串的长度。代码如下：

    public static int lengthOfLongestSubstring(String s) {
        int res = 0;
        // 判断字符串参数的长度，小于2则直接返回
        if(s.length() == 0 || s.length() == 1){
            return s.length();
        }
        // 外层循环遍历每一个下标，以当前下标为起始点找出无重复的最长子串
        for(int i = 0; i <  s.length(); i++){
            int index = i;
            StringBuffer sb = new StringBuffer();
            while (index < s.length()){
                // 如果之前没出现过，则加进sb
                if(sb.indexOf(String.valueOf(s.charAt(index))) == -1){
                    sb.append(s.charAt(index));
                    res = res > sb.length() ? res : sb.length();
                } else {
                    // 如果出现过则退出内循环，继续下一个外层循环
                    break;
                }
                index++;
            }
        }
        return res;
    }

思路二：利用 HashSet 中的 set.contains('a') 判断集合set中是否包含字符 a ，运用滑动窗口的思想。窗口分为左右边界，左边界初始值为 -1 ，表示窗口未开始移动，接着每次向右移动一次的同时移除最左边的值，接着最右边一直遍历到不包含重复字符的最长位置，期间动态记录不包含重复字符的最大长度。代码如下：

    public static int lengthOfLongestSubstring(String s) {
        int res = 0;
        if(s.length() == 0 || s.length() == 1){
            return s.length();
        }
        Set set = new HashSet<>();
        int index = -1; // 滑动窗口左侧
        for(int i = 0; i < s.length(); i++){ // i 为右侧
            // 除第一个元素外，每次移除上个左边界
            if(i != 0){
                set.remove(s.charAt(i - 1));
            }
            // 右边界一直遍历到不包含重复元素的最大值
            while (index + 1 < s.length() && !set.contains(s.charAt(index + 1))){
                set.add(s.charAt(index + 1));
                index++;
            }
            res = Math.max(res,set.size());
        }
        return res;
    }

思路二相比思路一的优点在于思路二每次不用重新从当前外循环下标统计新的无重复字符串，而是以华东窗口的形式，华东一次，移除上个下标位置并以上次遍历的基础上添加不重复的字符，这样从时间和空间的角度都大大提高了效率。