「力扣」第 3 题:无重复字符的最长子串(滑动窗口典型问题)
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
方法一:暴力解法
枚举这个字符串的所有子串;
对于每一个子串都判断一下这个子串是否有重复字符;
在从没有重复字符的所有子串中找出长度最长的那个,返回即可。
伪代码:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
int maxLen = 1;
for (int left = 0; left < len - 1; left++) {
for (int right = 0; right < len; right++) {
String subString = s.substring(left, right + 1);
if (subString 不包含重复元素){
maxLen = Math.max(maxLen, subString.length());
}
}
}
return maxLen;
}
}
方法二:滑动窗口
性质:如果在子区间 [left, right]
中有重复元素,[left, right + 1]
、[left, right + 2]
一直到 ``[left, len - 1]一定包含重复元素。此时就得考虑移动
left` 变量。
注意:
int[] hashMap = new int[128];
为了防止空格的出现,所以设置得大一点;只要是右边界
right
在窗口里出现了 $2$ 次,就得不断将左边界从窗口里删除,所以使用while
。
Java 代码:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len < 2) {
return len;
}
char[] charArray = s.toCharArray();
int left = 0;
int right = 0;
// 描述 [left, right) 里是否有元素的变量
int[] hashMap = new int[128];
// [left, right) 无重复的元素
int res = 1;
while (right < len) {
hashMap[charArray[right]]++;
if (hashMap[charArray[right] ] == 2) {
while (hashMap[charArray[right]] == 2) {
hashMap[charArray[left]]--;
left++;
}
}
right++;
res = Math.max(res, right - left);
}
return res;
}
}
Java 代码:
for
循环的写法:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len < 2) {
return len;
}
char[] charArray = s.toCharArray();
// 描述 [left, right) 里是否有元素的变量
int[] hashMap = new int[128];
// [left, right) 无重复的元素
int res = 1;
for (int left = 0, right = 0; right < len; right++) {
hashMap[charArray[right]]++;
if (hashMap[charArray[right]] == 2) {
while (hashMap[charArray[right]] == 2) {
hashMap[charArray[left]]--;
left++;
}
}
res = Math.max(res, right - left + 1);
}
return res;
}
}
方法三:滑动窗口 + 哈希表优化
思路:记录下每个字符出现的最新的下标。
Java 代码:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
// 特判
if (len < 2) {
return len;
}
int res = 1;
// key:数值,value:最新的下标
Map<Character, Integer> map = new HashMap<>(len);
char[] charArray = s.toCharArray();
int left = 0;
int right = 0;
// [left, right) 没有重复元素
while (right < len) {
Character c = charArray[right];
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1);
}
map.put(c, right);
right++;
res = Math.max(res, right - left);
}
return res;
}
}
- 使用数组代替哈希表
Java 代码:
public class Solution {
public int lengthOfLongestSubstring(String s) {
// 重复元素上一次出现的位置很重要
int len = s.length();
if (len < 2) {
return len;
}
int[] window = new int[128];
for (int i = 0; i < 128; i++) {
window[i] = -1;
}
char[] charArray = s.toCharArray();
int res = 1;
int left = 0;
// [left, right) 没有重复元素
for (int right = 0; right < len; right++) {
if (window[charArray[right]] != -1) {
left = Math.max(left, window[charArray[right]] + 1);
}
window[charArray[right]] = right;
// 注意理解这里为什么是 + 1
res = Math.max(res, right - left + 1);
}
return res;
}
}