0003.无重复字符的最长子串

题目链接3. 无重复字符的最长子串 - 力扣LeetCode### 题目描述给定一个字符串 s, 请你找出其中不含有重复字符的最长子串的长度。### 题目示例示例 1 :plain输入: s abcabcbb输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2 :plain输入: s bbbbb输出: 1解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3 :plain输入: s pwwkew输出: 3解释: 因为无重复字符的最长子串是 wke所以其长度为 3。 请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。### 解题思路1. **思路 1: ** 判断是否有重复字符对于每个字符s.charAt(j)如果它已经出现在map中说明当前窗口中存在重复字符此时需要更新左指针i使其跳到上一个重复字符的下一个位置即i Math.max(i, map.get(s.charAt(j)))。 更新哈希表将当前字符及其索引存入map即map.put(s.charAt(j), j)。 计算窗口长度当前窗口的长度是j - i如果长度大于记录的最大长度res则更新res。 返回结果循环结束后res就是最长无重复子串的长度。2.思路 2:这道题使用了滑动窗口双指针技巧。基本思路是1. 使用两个指针left和rightright用来扩展窗口left用来收缩窗口。2. 维护一个哈希表cnt来记录窗口内每个字符的出现次数。3. 当发现窗口内有重复字符时移动left指针直到窗口内的所有字符都唯一。4. 在每次扩展右指针时更新当前无重复字符子串的长度并记录最大值。### 题解代码1.题解代码 1 :javaclass Solution { public int lengthOfLongestSubstring(String s) { MapCharacter, Integer map new HashMap(); int i -1, res 0, len s.length(); for(int j 0; j len; j){ if(map.containsKey(s.charAt(j))) // 更新左指针 i i Math.max(i, map.get(s.charAt(j))); // 哈希表记录 map.put(s.charAt(j), j); // 更新结果 res Math.max(res, j - i); } return res; }}2.题解代码 2 :javaclass Solution { public int lengthOfLongestSubstring(String s) { char[] str s.toCharArray(); // 将字符串转换为字符数组 int n str.length, ans 0, left 0; int[] cnt new int[128]; // 假设字符集只有 128 个字符ASCII 字符集 for(int right 0; right n; right){ // 右指针遍历字符串 char c str[right]; // 当前字符 cnt[c]; // 记录字符 c 的出现次数 // 如果当前字符的出现次数大于 1说明有重复字符收缩窗口 while(cnt[c] 1){ cnt[str[left]]--; // 减少左指针指向的字符的计数 left; // 左指针右移缩小窗口 } // 更新答案计算当前窗口的长度 ans Math.max(ans, right - left 1); } return ans; // 返回最长子串的长度 }}### 复杂度分析1.题解1时空复杂度: 时间复杂度:O(n)其中n是字符串的长度。每个字符最多被访问两次分别由j和i两个指针访问。 空间复杂度:O(min(n, m))其中n是字符串的长度m是字符集的大小比如若字符集为 ASCII则m 128。 2.题解2时空复杂度: 时间复杂度O(n)其中n是字符串的长度。每个字符在右指针和左指针的过程中最多被访问两次因此时间复杂度为线性时间。 空间复杂度O(1)因为字符集大小是固定的最多 128 个字符使用了固定大小的cnt数组。因此空间复杂度是常数级别。