题目:给定一个字符串,找出其中无重复字符串的最长子串长度。
例如 :
输入:“abcabcbb”
输出: 3
说明: “abc”为其中的最长无重复子串,长度为3
题解:
- 使用两个指针,左指针指向当前子串起始下标,右指针指向当前子串尾部下标。右指针每移动一位,计算当前的子串长度。
- 在指针移动过程中,需要记录当前子串以存在的字符和下标,比如用Map存储。
- 当右指针每移动一次,需判断当前子串中是否已经存在当前指向的字符。若已存在,需将左指针移动到当当前字符的下标。再继续移动右指针,直至遍历完字符串。
题解代码如下:
public class Solution {
public static int lengthOfLongestSubstring(String s) {
int length = s.length();
int ans = 0;
// current index of character
Map<Character, Integer> map = new HashMap<>();
// try to extend the range [left, right]
int left = 0;
for (int right = 0; right < length; right++) {
Character c = s.charAt(right);
if (map.containsKey(c)) {
left = Math.max(map.get(c), left);
}
ans = Math.max(ans, right - left + 1);
map.put(c, right + 1);
}
return ans;
}
}
该题还另外一种更优解法,在上方解法中,借助了Map。但在使用Map的同时,也造成了性能的损耗。换个思路,因为给出的字符串中,均为英文字母,a-z或A-Z。其在ASCII表中,A-Z对应65-90,a-z对应97-122。因此可借助ASCII表,使用基本数据类型数据来代替Map。其做法如下:
public class Solution {
public static int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
// current index of character
int[] index = new int[128];
// try to extend the range [left, right]
for (int right = 0, left = 0; right < n; right++) {
// if index[s.charAt(right)] > left , means current char is repeat
left = Math.max(index[s.charAt(right)], left);
ans = Math.max(ans, right - left + 1);
index[s.charAt(right)] = right + 1;
}
return ans;
}
}