力扣 3.无重复字符的最长子串

Problem: 3.无重复字符的最长子串

思路

滑动窗口

解题过程

通过滑动窗口来判断最长字串，起初窗口的左（l）右（r）边界都在第一个字母位置，并且将字母存入一个Map数组用来判重（也可以用Set）。

之后就开始滑动，右边界一直往右扩大，扩大的同时把经过的字母存入Map数组，存入之前判断是否有已经存在的字母了，如果说明以左边这个字母（s[l]）为开头的无重复子串已经达到最长子串了，然后左边界就需要开始缩减（向右移动），直到找到与右边界目前所处位置的字符相同的字符为止，然后把该字符剔除，然后左边界再右移一位，从该位置当作开头，右边界接着重新继续滑动。

依次反复，每找到依次重复的，当前的长度就和ans取一次max。

复杂度

• 时间复杂度: O(n)

• 空间复杂度: O(n)

Code

class Solution { public int lengthOfLongestSubstring(String s) { int ans = 1; int len = s.length(); if (len == 0) ans = 0; int l = 0; int r = 0; Map<Character,Integer> count = new HashMap<>(); while(r < len) { if (count.containsKey(s.charAt(r))) { ans = Math.max(ans, r - l); while(l < len && s.charAt(l) != s.charAt(r)) { count.remove(s.charAt(l)); l++; } count.remove(s.charAt(l)); l++; } else { count.put(s.charAt(r),1); r++; } } ans = Math.max(ans, len - l); return ans; } }

大佬们有更好方法希望能评论区指点一下~