LeetCode刷题笔记 | 3 | 无重复字符的最长子串 | 双指针 | 滑动窗口 | 2025兴业银行秋招笔试题 | 哈希集合
🌈个人首页： 神马都会亿点点的毛毛张
1.题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
- 0 < = s . l e n g t h < = 5 ∗ 1 0 4 0 <= s.length <= 5 * 10^4 0<=s.length<=5∗104
s由英文字母、数字、符号和空格组成
2.题解
- 盲猜暴力解法肯定超时，毛毛张就不在这里介绍了
- 这个题目只需要最长子串的长度，做完可以尝试一下这道题目：LeetCode:67.最小覆盖子串
2.1 双指针-哈希集合
class Solution {public int lengthOfLongestSubstring(String s) {// 使用一个Set来存储当前子串中的字符Set<Character> set = new HashSet<>();// 初始化左右指针和最大长度int left, right;int maxLen = 0;// 从左到右遍历字符串for (left = 0, right = 0; right < s.length(); right++) {// 获取当前字符Character c = s.charAt(right);// 如果当前字符不在Set中，更新最大长度if (!set.contains(c)) {maxLen = Math.max(maxLen, right - left + 1);}// 如果当前字符在Set中，则移动左指针直到没有重复字符while (set.contains(c)) {set.remove(s.charAt(left));left++;}// 将当前字符添加到Set中set.add(c);}// 返回最大长度return maxLen;}
}
2.2 双指针-哈希数组
- 如果能用哈希集合，那么大概率也可以使用哈希数组
class Solution {public int lengthOfLongestSubstring(String s) {// 使用一个大小为128的整数数组来记录字符出现的次数int[] arr = new int[128];// 初始化左右指针和最大长度int left, right;int maxLen = 0;// 从左到右遍历字符串for (left = 0, right = 0; right < s.length(); right++) {// 获取当前字符char c = s.charAt(right);// 如果当前字符在数组中的计数为0，更新最大长度if (arr[c] == 0) {maxLen = Math.max(maxLen, right - left + 1);}// 如果当前字符在数组中的计数不为0，则移动左指针直到没有重复字符while (arr[c] != 0) {arr[s.charAt(left)]--;left++;}// 将当前字符的计数加1arr[c]++;}// 返回最大长度return maxLen;}
}