LeetCode - 3
题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
解题思路
双指针
使用快慢指针i、j 来指向子串的头和尾,用k指针在i、j之间遍历寻找是否有重复的字母出现,有重复则更新i,即子串的起始位置。
int i = 0, max = 0;
char[] chars = s.toCharArray();
for (int j = 0; j < s.length(); j++) {
for (int k = i; k < j; k++)
if (chars[k] == chars[j]) {
i = k + 1;
break;
}
max = Math.max(j - i + 1, max);
}
return max;
滑动窗口
滑动窗口是数组/字符串问题中常用的抽象概念。
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 $$[i, j)$$(左闭右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。
例如,我们将 $$[i, j)$$ 向右滑动 1个元素,则它将变为 $$[i+1,j+1)$$(左闭右开)。
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j));
j++;
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i));
i++;
}
}
return ans;
}
改进的滑动算法
public int lengthOfLongestSubstring(String 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);
}
ans = Math.max(ans, end - start + 1);
map.put(s.charAt(end), end + 1);
}
return ans;
}
使用数组来代替Map
当字符集比较小的时侯,我们可以用一个整数数组作为直接访问表来替换 Map。
常用的表如下所示:
- int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’ ,如果建一个26位的数组,需要将 char-65 或 char-97来保证 A、a 从index = 0 开始
- int [128] 用于ASCII码,一般用这个就够了
- int [256] 用于扩展ASCII码
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // 当前字母char的下标,如果是a-z的话直接从97开始
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i); //不用强转成int,能自动识别
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
感谢:LeetCode
部分参考自:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetcod/