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

题目链接 => 戳这里

题目描述
这道题感觉还是比较经典的，具体解析建议点入上方的题目链接去看一下，会比较有帮助；

解法1：“一力破万法”

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int ans = 0;
        for (int i = 0; i < length; i++) {
            // 注意这里需要使用的<= 号，因为AllUniqueChar中i取不到end的值
            for (int j = i+1; j <= length; j++) {
                if (AllUniqueChar(s, i, j)) {
                    ans = Math.max(ans, j-i);
                }
            }
        }
        return ans;
    }

    private static boolean AllUniqueChar(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        // 上面的注释说的就是这里
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) {
                return false;
            }
            set.add(ch);
        }
        return true;
    }
}

暴力破解法，就是罗列了字符串的所有子串，然后每一个都检查一下有没有重复字符，如果没有，就跟已有的最长字符串长度值比较，比它大则更新数据；

解法2：滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int len = s.length();
        int ans = 0, i = 0, j = 0;
        while(i < len && j < len) {
            if (!set.contains(s.charAt(j))) {
                // 这里的j++
                set.add(s.charAt(j++));
                ans = Math.max(ans, j-i);
            } else {
                // 和这里的i++用得还是比较妙的
                // i++ 把窗口往右滑动了
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

原本想画图来着。。。但是夜深了，就算了，下次有空再补。。。

解法3：滑动窗口的优化版

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0, i = 0, j = 0;
        int len = s.length();
        while (i < len && j < len) {
            if (map.containsKey(s.charAt(j))) {
                // 这一步是防止窗口左移
                i = Math.max(i, map.get(s.charAt(j)));
            }
            // 索引值加减，注意+1
            ans = Math.max(ans, j-i+1);
            // 更新重复元素的最新索引
            map.put(s.charAt(j), j+1);
            j++;
        }
        return ans;
    }
}

下次补图。。。