目录一、题目解析示例 1示例 2示例 3二、算法原理解法一暴力枚举 哈希表O(n²)解法二滑动窗口推荐O(n)滑动窗口的核心步骤三、编写代码Javafor循环写法推荐while循环写法四、总结OJ链接无重复字符的最长子串哈喽大家好今天咱们来啃一道经典的算法题——无重复字符的最长子串。这道题在 LeetCode 上是第 3 题难度中等但绝对是必练的滑动窗口入门题一、题目解析先看题目描述给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。注意关键词子串必须是连续的和无重复字符。示例 1输入s abcabcbb输出3解释因为无重复字符的最长子串是abc所以长度为 3。示例 2输入s bbbbb输出1解释因为无重复字符的最长子串是b所以长度为 1。示例 3输入s pwwkew输出3解释因为无重复字符的最长子串是wke所以长度为 3。注意pwke是子序列不是子串小贴士子串 vs 子数组 → 都是连续的一段别被“子序列”带偏了二、算法原理这道题有几种解法我们重点讲两种解法一暴力枚举 哈希表O(n²)枚举所有子串用哈希表判断是否有重复字符。时间复杂度高不推荐但可以作为理解题意的起点。解法二滑动窗口推荐O(n)利用“窗口”思想维护一个无重复字符的连续区间。用两个指针left和right表示窗口左右边界。用一个数组或哈希表记录每个字符出现的次数。滑动窗口的核心步骤初始化left 0,right 0进窗口让s[right]进入窗口 →hash[s[right]]判断如果hash[s[right]] 1→ 说明有重复出窗口从左边开始删直到重复字符被移除 →hash[s[left]]--更新结果ret Math.max(ret, right - left 1)移动右指针right关键点窗口内始终是无重复字符的一旦重复就收缩左边界直到恢复无重复状态。三、编写代码Java我整理了两种写法for循环写法更推荐结构清晰易读也保留了while循环写法方便你对比学习。for循环写法推荐class Solution { public int lengthOfLongestSubstring(String ss) { // 先转换为字符数组 char[] s ss.toCharArray(); // 数组模拟哈希表存储每个字符出现的次数 // 也是滑动窗口需要维护的数据 int hash[] new int[128]; int n ss.length(); int len 0; for(int left 0, right 0; right n; right) { // 入窗口 hash[s[right]]; // 判断 while(hash[s[right]] 1) { // 出窗口 hash[s[left]]--; } // 更新结果 len Math.max(len, right - left 1); } return len; } }while循环写法class Solution { public int lengthOfLongestSubstring(String ss) { char[] s ss.toCharArray(); int[] hash new int[128]; int left 0, right 0; int ret 0; int n ss.length(); while (right n) { // 入窗口 hash[s[right]]; // 判断 while (hash[s[right]] 1) { // 出窗口 hash[s[left]]--; } // 更新结果 ret Math.max(ret, right - left 1); // 让下一个字符进入窗口 right; } return ret; } }四、总结这道题是滑动窗口的经典入门题核心是用双指针维护窗口用数组/哈希表记录字符频次遇到重复就收缩左边界每次更新最大长度时间复杂度O(n)空间复杂度O(1)因为字符集固定128
10.滑动窗口解决：无重复字符的最长子串 | LeetCode 3 Java 题解
目录一、题目解析示例 1示例 2示例 3二、算法原理解法一暴力枚举 哈希表O(n²)解法二滑动窗口推荐O(n)滑动窗口的核心步骤三、编写代码Javafor循环写法推荐while循环写法四、总结OJ链接无重复字符的最长子串哈喽大家好今天咱们来啃一道经典的算法题——无重复字符的最长子串。这道题在 LeetCode 上是第 3 题难度中等但绝对是必练的滑动窗口入门题一、题目解析先看题目描述给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。注意关键词子串必须是连续的和无重复字符。示例 1输入s abcabcbb输出3解释因为无重复字符的最长子串是abc所以长度为 3。示例 2输入s bbbbb输出1解释因为无重复字符的最长子串是b所以长度为 1。示例 3输入s pwwkew输出3解释因为无重复字符的最长子串是wke所以长度为 3。注意pwke是子序列不是子串小贴士子串 vs 子数组 → 都是连续的一段别被“子序列”带偏了二、算法原理这道题有几种解法我们重点讲两种解法一暴力枚举 哈希表O(n²)枚举所有子串用哈希表判断是否有重复字符。时间复杂度高不推荐但可以作为理解题意的起点。解法二滑动窗口推荐O(n)利用“窗口”思想维护一个无重复字符的连续区间。用两个指针left和right表示窗口左右边界。用一个数组或哈希表记录每个字符出现的次数。滑动窗口的核心步骤初始化left 0,right 0进窗口让s[right]进入窗口 →hash[s[right]]判断如果hash[s[right]] 1→ 说明有重复出窗口从左边开始删直到重复字符被移除 →hash[s[left]]--更新结果ret Math.max(ret, right - left 1)移动右指针right关键点窗口内始终是无重复字符的一旦重复就收缩左边界直到恢复无重复状态。三、编写代码Java我整理了两种写法for循环写法更推荐结构清晰易读也保留了while循环写法方便你对比学习。for循环写法推荐class Solution { public int lengthOfLongestSubstring(String ss) { // 先转换为字符数组 char[] s ss.toCharArray(); // 数组模拟哈希表存储每个字符出现的次数 // 也是滑动窗口需要维护的数据 int hash[] new int[128]; int n ss.length(); int len 0; for(int left 0, right 0; right n; right) { // 入窗口 hash[s[right]]; // 判断 while(hash[s[right]] 1) { // 出窗口 hash[s[left]]--; } // 更新结果 len Math.max(len, right - left 1); } return len; } }while循环写法class Solution { public int lengthOfLongestSubstring(String ss) { char[] s ss.toCharArray(); int[] hash new int[128]; int left 0, right 0; int ret 0; int n ss.length(); while (right n) { // 入窗口 hash[s[right]]; // 判断 while (hash[s[right]] 1) { // 出窗口 hash[s[left]]--; } // 更新结果 ret Math.max(ret, right - left 1); // 让下一个字符进入窗口 right; } return ret; } }四、总结这道题是滑动窗口的经典入门题核心是用双指针维护窗口用数组/哈希表记录字符频次遇到重复就收缩左边界每次更新最大长度时间复杂度O(n)空间复杂度O(1)因为字符集固定128
