当前位置：首页 > news >正文

008无重复字符的最长子串

news 2026/5/2 6:21:32

无重复字符的最长子串

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public int lengthOfLongestSubstring(String s) { int length = s.length(); if(length==0){ return 0; } Map<Character,Integer> map = new HashMap<>(length);//维护每个字符最近出现的下标 int l=0, r=l+1, index=l; int ans=1; map.put(s.charAt(0),0); while(r<length){ while(r<length&&!map.containsKey(s.charAt(r))){ map.put(s.charAt(r),r); r++; } ans=Math.max(ans,r-l); if(r>=length){ break; } index=map.get(s.charAt(r))+1; while(l<index){ map.remove(s.charAt(l++)); } map.put(s.charAt(r),r); r++; } return ans; }

分析：代码的时间复杂度为O(n)，空间复杂度为O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符）。我的思路是利用HashMap存储每次访问过的字符，并维护这个字符最近出现的位置；再利用两个指针l和r，指向未重复字符串的起始位置，r从l的下一个位置开始往右移动，直到遇到HashMap中重复的字符，更新答案，然后让l移动到重复字符最近出现的位置的后一个位置并同步删除HashMap中字符的记录，最后更新重复字符最近出现的记录即可。

看了官方题解后的解答：

public int lengthOfLongestSubstring(String s) { int length = s.length(); if(length==0){ return 0; } Set<Character> set = new HashSet<>(); int l,r; int ans=0; set.add(s.charAt(0)); for(l=0,r=l+1; r<=length; l++){ while(r<length&&!set.contains(s.charAt(r))){ set.add(s.charAt(r)); r++; } ans=Math.max(ans,r-l); if(r==length){ break; } set.remove(s.charAt(l)); } return ans; }

分析：

1、代码的时间复杂度为O(n)，空间复杂度为O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符）。

2、采用滑动窗口。

3、用HashSet记录字符。

4、思路：根据每一个字符当作开头时最长的字符串的长度取最大值即为答案。且满足“当以索引为k的字符作为开头时，假设直到k+n才遇到重复的字符，那么以k+1开头的字符串直到k+n-1都不会遇到重复的字符”，根据这个条件，我们可以实现一直往后遍历而不会回退的情况，从而实现O(n)的时间复杂度解决问题。

5、我的解答与官方解答的区别在于，我用hashSet不仅保存了字符，还维护了字符最近出现位置的索引，每一次遇到重复字符后我选择直接跳到这个字符最近出现的位置，而非将每一个元素都当作一次字符串的开头计算一遍。

6、经过与官方题解比较发现，我才用的方法更符合双指针的特点。