题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
提示：
- $0 <= s.length <= 5 * 10^4$
- s 由英文字母、数字、符号和空格组成
题解
1、滑动窗口
1、滑动窗口算法
- 哈希表
- 遇到重复元素，更新窗口左侧值
- 计算不重复子串的长度
使用hash map
public int lengthOfLongestSubstring(Srting s) {
int n = s.length(),ans = 0;
Map<Character,Integer> map = new HashMap<>();
for (int end = 0,start = 0;end < n;end++) {
char alpha = s.charAt(end);
if (map.containsKey(alpha)) {// 包含字母
start = Math.max(map.get(alpha),start);// 更新start
}
// 更新结果
ans = Math.max(ans,end - start + 1);
map.put(s.charAt(end),end+1);// 更新字母的位置
}
return ans;
}
用数组代替Map
//
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
// 更新
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
使用hash set
- 窗口左边界逐步增加
- 窗口检查：
- 没有重复元素，新字符加入set中，增加窗口右边界
- 有重复元素，本轮窗口结束，计算窗口长度
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
// 窗口扩增
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
