LeetCode-无重复字符的最长子串（3）

题目描述：

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

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> occ=new HashSet<Character>();
        int len=s.length();
        int rk=0,ans=0;

        for(int i=0;i<len;i++) {

            if(i!=0) {
                occ.remove(s.charAt(i-1));
            }

            while(rk<len && !occ.contains(s.charAt(rk))) {

                occ.add(s.charAt(rk));
                rk++;
            }
            ans=Math.max(ans,rk-i);
        }
        return ans;
    }
    

    }



    

思路： 这题看到一般会想到使用双层循环，一层顺序遍历字符串字符，一层遍历每个字符开头的不重复子串，但是这样显然会超时。思考了挺久看了官方题解，算是学到了一种方法。题解中的思路就是首先通过一个for循环从字符串的每个字符开始记录不重复子串，这里的记录不重复子串也就是在每层循环里再套一个while循环来遍历每个起始字符后的字符直至出现重复。那么为什么这里明明有两层循环，方法却不超时，这就是官方题解的巧妙之处。在理解这个巧妙点之前必须先知道一个思想，这里直接贴官方题解的截图。

通过上图我们知道，起始字符后的不重复字符下一个起始字符不需要处理，因为前一个起始字符后的不重复字符对于下一个起始字符来说肯定也是不重复的，这样就减少了很多次运行从而避免超时。
代码中是定义了记录不重复子串尾部位置的rk，通过rk与i的关系可以计算出子串长度，每次while循环后都进行比较。
为了实现上述操作，因此在每次的for循环在集合中删除前一个起始字符，并且通过rk的指向将不重复子串的字符加入集合，对于下一个起始字符可以直接接着rk的指向添加字符。