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

今天继续给大家分享一道力扣的做题心得今天这道题目是 无重复字符的最长子串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;
        
    }
}

解题思路

1. 数据结构选择：使用HashSet来存储当前窗口中的字符，以实现O(1)时间复杂度的重复性检查。

2. 双指针维护窗口：

   • left指针标记窗口的起始位置。

   • right指针不断扩展窗口的结束位置。

3. 窗口扩展与收缩：

   • 当right指向的字符不在集合中时，将其加入集合，并扩展窗口（right右移）。

   • 若字符已存在，则通过移动left指针逐个移除字符，直到重复字符被移出窗口。

4. 更新最大长度：每次成功扩展窗口后，计算当前窗口长度并更新最大值。

题解的正确性分析

• 确保窗口唯一性：通过HashSet的检查和指针调整，保证窗口内字符始终唯一。

• 时间复杂度O(n)：每个字符最多被left和right访问一次，总体操作次数为2n。

• 空间复杂度O(min(n, m))：m为字符集大小，例如ASCII字符集时为O(1)。

解题关键点

• 滑动窗口机制：通过动态调整窗口边界，高效地遍历所有可能的子串。

• 即时更新最大值：仅在窗口扩展时更新最大值，避免无效计算。

• 逐步调整左指针：确保重复字符完全移出后，继续扩展窗口，不漏解。

4，总结

        感谢大家的阅读，希望这篇解题心得能为大家带来一些收获，我们共同进步！大家的点赞就是我的动力谢谢大家，还有什么更优解或者问题欢迎大家在评论区讨论分享！