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

我开始做这题的时候是按之前我做“最长递增子序列”的思路走的。

想的是再开一个数组储存以【字符串每个字符为开头的无重复子序列】的长度，这样可以找到最长的那个子串的头，然后按leetcode.1的题目思路，对那个字符串做一次哈希表的添加和查重就over了。

class Solution {
    public int Check(String s,int i) {
        HashMap<Character, Integer> strLength=new HashMap<>();
        int j=0;
        for(;i<s.length();i++) {
            if(strLength.containsKey(s.charAt(i))) {
                break;
            }
            else {
                strLength.put(s.charAt(i), i);
            }
            j++;
        }
        return j;
    }
    public int lengthOfLongestSubstring(String s) {
        int len[]=new int[s.length()];
        int max=0;
        int index=0;
        for(int i=0;i<s.length();i++) {
            len[i]=Check(s,i);
            if(max<len[i]) {
                index=i;
                max=len[i];
            }
        }
        int lengTh=Check(s,index);
        return lengTh;

    }
}

想法简单，然而....跑了83ms

于是我找了一下题解，学习了“滑动窗口算法”。

其实也就是在哈希表的添加查重上做了一些改动。即定义一下已存入的一组元素的开头和结尾的索引，例如[i,j)，然后往里面添加不重复键值来拓宽j的边界，一旦发现重复就通过增加i来缩小范围，直到不重复为止。期间用一个max不断更新来记录区间的【最大】距离。就这样对整个数组或者字符串扫描完成以后，得到的max就是最大的子串长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
       int n=s.length();
        int i = 0,j=0;
        int ans=0;
        HashMap<Character, Integer> str=new HashMap<>();
        while(i<n&&j<n) {
            if(!str.containsKey(s.charAt(j))) {
                str.put(s.charAt(j), j-i);
                j++;
                ans=Math.max(ans, j-i);
            }
            else {
                str.remove(s.charAt(i));
                i++;
            }
        }
        return ans;
    }
}

这次跑了13ms，给力嗷。

其实这个算法还有继续优化的空间，可参看https://www.codercto.com/a/63236.html