Leetcode-003-无重复字符的最长子串

无重复字符的最长子串

滑动窗口法

import java.util.ArrayList;

public class LengthOfLongestSubstring_003 {
    public static void main(String[] args) {
        String str = new String("twwwwwwwwwwwwwt");

        int len = lengthOfLongestSubstring(str);
        System.out.println(len);
    }

    public static int lengthOfLongestSubstring(String s) {
        int len = 0;
        int left = 0;
        String[] strs = s.split("");
        //存放字符串
        StringBuilder sb = new StringBuilder();
        //字符长度为0，结果为0
        if(s.equals("")) return  0;
        for (int i = 0; i < strs.length; i++) {
            //有重复字符出现，左侧范围加一
            left = Math.max(left++, sb.lastIndexOf(strs[i])+1);
            //添加下一个字符
            sb.append(strs[i]);
            len = Math.max(len, i-left+1);
        }
        return len;
    }
}

效率过差，耗内存也耗时间，猜测是 lastIndexOf 和 String 扩容机制导致的：

• lastindexof 每次遍历全部内容；
• String 扩容是创建了新的对象，占用了更多的空间；
• 可以用 hashmap，或者参考题解，用 int[] 数组 计录 ASC II 码的方式代替 String 的对比方法；