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

力扣经典题目之3无重复字符的最长子串

article 2025/2/4 1:52:29

今天继续给大家分享一道力扣的做题心得今天这道题目是 无重复字符的最长子串3. 无重复字符的最长子串 - 力扣（LeetCode）

题目如下，点击上面题目名称即可跳转到力扣对应题目页面也来挑战这道题

1，题目分析

此题目不难，就是给我们了一个内容随机的一个字符串，在这其中找到一个不含重复字符的子串，如果没有做过此类找子串的题目那么我们就要学习一下专门用于解决此类型题的一个解题方法，叫做滑动窗口，这个方法在用于解决找各种子串问题上是一个非常好的方法下面我们来看如果使用此方法快速解决这道题目

2，解题思路

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        // 使用双指针的方法来解决问题
        int left = 0; int right = 0;int maxLength = 0;

        // 循环遍历字符
        while(right < s.length()){
            char  a = s.charAt(right);

            // 如果字符不在当前子串中
            if(!set.contains(a)){
                set.add(a);
                right++;
            // 更新最大长度
            maxLength = Math.max(maxLength,right-left);
            }else{
                // 如果当前的子串中存在此字符，则移除左指针指向的字符并且移动左指针
                set.remove(s.charAt(left));
                left++;

            }

        }
        return maxLength;
        
    }
}

解题思路

数据结构选择：使用HashSet来存储当前窗口中的字符，以实现O(1)时间复杂度的重复性检查。
双指针维护窗口：
- left指针标记窗口的起始位置。
- right指针不断扩展窗口的结束位置。
窗口扩展与收缩：
- 当right指向的字符不在集合中时，将其加入集合，并扩展窗口（right右移）。
- 若字符已存在，则通过移动left指针逐个移除字符，直到重复字符被移出窗口。
更新最大长度：每次成功扩展窗口后，计算当前窗口长度并更新最大值。