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

可变字符串法

class Solution {
    public int lengthOfLongestSubstring(String s) {

        /**
         * 使用可变字符串
         * 为了方便对子串进行增删，创建一个StringBuilder对象
         * 但同时为了利用String类的indexOf()方法判断子串中是否包含重复的元素，在每次循环前将其再转换为字符串
         */
        int right = 0;
        StringBuilder str = new StringBuilder();
        int max = 0;

        while (right < s.length()){

            String temp = str.toString();

            if (temp.indexOf(s.charAt(right)) < 0){

                str.append(s.charAt(right));
                max = Math.max(str.length(), max);
                right++;
            }

            /**
             * 如果出现了重复元素，删除子串的第一个字符再去判断
             */
            else {
                str.deleteCharAt(0);
            }
        }

        return max;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

优化1——减少排除重复元素区间的次数

class Solution {
    public int lengthOfLongestSubstring(String s) {

        /**
         * 使用可变字符串
         * 为了方便对子串进行增删，创建一个StringBuilder对象
         * 但同时为了利用String类的indexOf()方法判断子串中是否包含重复的元素，在每次循环前将其再转换为字符串
         */
        int right = 0;
        StringBuilder str = new StringBuilder();
        int max = 0;

        while (right < s.length()){

            String temp = str.toString();
            int flag = temp.indexOf(s.charAt(right));

            if (flag < 0){

                str.append(s.charAt(right));
                max = Math.max(str.length(), max);
                right++;
            }

            /**
             * 如果出现了重复元素，用flag记录下重复的位置，一次性删去该重复元素之前的所有元素
             */
            else {
                str.delete(0, flag + 1);
            }
        }

        return max;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {

        /**
         * 滑动窗口
         * 由于字符串的长度可能为0，因此right初始值为-1
         * 因为每个字符等同于其ASCII码对应的整型，所以可以定义一个256的数组来存储每个字符出现的次数
         */
        int left = 0;
        int right = -1;
        int[] count = new int[256];
        int max = 0;

        while (left < s.length()){

            /**
             * 因为right从-1开始，因此作为索引时要加1
             * 如果right + 1没有越界且当前元素没有重复，right就往后移动
             * 否则让left的元素次数减1，并且left右移，直到将那个重复元素排除出当前区间
             */
            if (right + 1 < s.length() && count[s.charAt(right + 1)] == 0){

                right++;
                count[s.charAt(right)]++;
            }
            else {

                count[s.charAt(left)]--;
                left++;
            }

            max = Math.max(max, right - left + 1);
        }

        return max;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/