算法学习:leetcode3. 无重复字符的最长子串

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

示例 1:

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

思路:这里还是用到了两个指针,左指针和右指针,左指针负责从开头依次取一个字符作为本次检查的开头字符,例如字符串”abcabcbb”,左指针处理的开头字符依次是(括号括起来的字符):

(a)bcabcbb

a(b)cabcbb

ab(c)abcbb

abc(a)bcbb

abca(b)cbb

一直到最后

右指针则是基于左指针取得首字符,依次向后取字符,检查是否和前面的字符是否重复。

(a)bcabcbb

右指针依次从开头往后取字符:a、b、c、a

例如:首次检查,左指针从第一个a开头,也就是从字符串开头开始,右指针也是从开头开始,右指针依次取每个字符,检查与之前的字符是否重复。

字符串:abcabcbb

右指针先取a(不重复),再取b(不重复),再取c(不重复),当前取到了不重复的字符串“abc”,这时,再向后取一个字符是:a,这是判断和之前的字符重复了,那么以开头那个a开头判断的不重复字符串长度为3,本地循环结束,继续下次循环。

结合代码来看,会比较清晰。

public int lengthOfLongestSubstring(String s) {
        //结果长度
        int result = 0;
        //右侧指针,这里用-1是方便下边循环中的递进计算
        int rk = -1;
        //用于检测字符是否重复
        Set<Character> hs = new HashSet<>();
        //依次移动开头字符,i相当于左侧指针
        for(int i=0; i<s.length(); i++) {
            //只要下一个字符和HashSet中的字符不重复,则一直往set中放
            //如果发现重复了,则rk也不移动,等下一个i循环过来,
            //继续从rk当前位置检查是否重复
            while(rk+1 < s.length() && !hs.contains(s.charAt(rk+1))) {
                hs.add(s.charAt(rk+1));
                rk++;
            }
            //检查当前不重复字符串长度是否有更大的值
            if(rk-i+1 > result) {
                result = rk-i+1;
            }
            hs.remove(s.charAt(i));
        }
        return result;
    }