算法一：暴力

暴力找出所有的子串时间复杂度为$O(n^2)$，对于每个子串遍历一遍查看有无重复元素时间复杂度为$O(n)$，所以总的时间复杂度为$O(n^3)$，会超时，所以想一下如何做优化。

算法二：滑动窗口

将左右指针初始化成0，左指针每次向右移动1，右指针一直向右移动直到碰到重复的元素，这样一定能找到答案，因为这样是按照子串的开头遍历的，所以一定包含所有的情况。时间复杂度：因为i和j分别最多移动n次，所以为$O(2n)$

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> hash = new HashSet<>();
        int ans = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            if (i > 0) {
                hash.remove(s.charAt(i - 1)); // 因为i向右移动1，那么i-1位置上的字符从hash中删除
            }
            while (j < s.length() && !hash.contains(s.charAt(j))) { // 只要j不超过长度并且无重复元素则一直向右移动
                hash.add(s.charAt(j)); // 将该字符加到hash中
                j++;
            }
            ans = Math.max(ans, j - i); // 这里要注意的是不是j-i+1因为j停止时是包含重复元素的所以要再减去1
        }
        return ans;
    }
}

以右指针遍历，参考yxc

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        for (int j = 0, i = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                int k = i;
                i = map.get(s.charAt(j)) + 1;
                for (int u = k; u < i; u++) {
                    map.remove(s.charAt(u));
                }
            }
            map.put(s.charAt(j), j);
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}