【LeetCode】3. 无重复字符的最长子串（Java）

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

解法一

暴力破解

class Solution { public int lengthOfLongestSubstring(String s) { //set char[] ch = s.toCharArray(); Set<Character> set = new HashSet<>(); int maxLen = 0; int len = 0; for (int i = 0; i < ch.length; i++) { for (int j = i; j < ch.length; j++) { //添加失败说明出现重复字符，进入下个循环 if (!set.add(ch[j])) { //比较长度 if (len > maxLen) { maxLen = len; } //初始化 len = 0; set.clear(); break; } else { len++; } } } return Math.max(maxLen, len); } }

暴力破解效率差，通过题解区画手大鹏大佬的题解学会了滑动窗口。

解法二

滑动窗口

class Solution { public int lengthOfLongestSubstring(String s) { //滑动窗口 //key为字符，value为下标 //如果出现重复值，更新下标 Map<Character, Integer> map = new HashMap<>(); int len = 0; for (int start = 0, end = 0; end < s.length(); end++) { char c = s.charAt(end); //如果添加的值已存在，更改start的位置 if (map.containsKey(c)) { //更改start的位置 start = Math.max(map.get(c) + 1, start); } //比较长度 len = Math.max(len, end - start + 1); //不存在就把字符保存到map中，存在就更新下标 map.put(c, end); } return len; } }