LeetCode第三题：无重复字符的最长子串
2019-10-08 本文已影响0人
躺在家里干活
题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
说明
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答
一般思路
- 将字符串转化为字符数组
- 问题转化：
-
找出
相同字符之间的下标差，并且后一个字符之前不能有相同的字符
abcdb中字符串abcd和bcd符合要求;
abcdbefb中字符串bcdbef不符合要求，因为bcdbef中在最后一个字符b之前，有相同的字符b，但是子串bef是符合要求的; -
找出最大的下标差
- 简单思路
- 循环整个数组
- 在每次循环中保存一个
key(具体字符):value(下标)，并且判断之前是否保存过这个字符 - 如果保存过，先判断两个下标之间是否有
相同的字符，如果有就需要处理这种情况（取到没有重复字符的下标位置），之后计算当前下标到之前保存的下标之间的距离 - 如果字符没有保存过，就保存字符
public static int getNoRepeat(String s) {
char[] chars = s.toCharArray();
// 用来保存 字符:下标
Map<Character, Integer> map = new HashMap<>();
// 最长无重复字符的子串长度
int maxLong = 0;
// 当前可用的下标
// 对于[abcdedf]
// 当下标是0至4的时候，effectiveIndex = -1
// 当下标到5（字符d）的时候，effectiveIndex = 3 (因为前一个d的坐标是3)
int effectiveIndex = -1;
// 每次循环的最大值
int tempMax = 0;
for (int i = 0; i < chars.length; i++) {
// 获取下标
int mapValue = map.getOrDefault(chars[i], -1);
// -1 表示map中没有当前字符
if (mapValue == -1) {
tempMax = i - effectiveIndex;
} else {
// 如果map中有这个字符，并且这个字符的小标大于 effectiveIndex
// [abcdefda] 中，当循环到第二个字符a的时候，map的值是0，但是effectiveIndex为3，此时不需要更改effectiveIndex
// [abcdefxdxyz] 中，当循环到第二个x时，e12x = 3,此时mapValue = 6,需要更换e12x,否则子串中符号x会重复
if (mapValue > effectiveIndex) {
tempMax = i - mapValue;
effectiveIndex = mapValue;
} else {
tempMax = i - effectiveIndex;
}
// 判断此次的长度是否大于当前最大长度
if (tempMax > maxLong) {
maxLong = tempMax;
}
// 向map中增加元素
map.put(chars[i], i);
}
return maxLong;
}
执行之后，击败76% 😣
优化思路
想着是因为map存取的时候消耗了性能，使用数组+ASCII码的方式替换写法
public static int getNoRepeat(String s) {
char[] chars = s.toCharArray();
int[] map = new int[129];
for (int i = 0; i < map.length; i++) {
map[i] = -1;
}
int maxLong = 0;
int effectiveIndex = -1;
int tempMax;
for (int i = 0; i < chars.length; i++) {
int key = chars[i];
int index = map[key];
// 有值，说明可以更新
if (index > effectiveIndex) {
effectiveIndex = index;
}
tempMax = i - effectiveIndex;
if (tempMax > maxLong) {
maxLong = tempMax;
}
map[key] = i;
}
return maxLong;
}
执行代码，击败99.39%
打完收工
更多说明
ASCII的应用可能会让人觉得知识凑巧，万一有汉字，其它特殊字符怎么办，其实这就是一种思路，只要元素是已经的，有限的，就可以使用这种思路，如果会有特殊字符，我们也可以自定义特殊字符对应的数值。
其他语言解法
1. JS
// 方法一
var lengthOfLongestSubstring = function(s) {
var effectIndex = -1;
var len = 0;
var map = [];
for (var j = 0; j < 129; j++) {
map[j] = -1;
}
for (var i = 0; i < s.length; i++) {
var key = s[i].charCodeAt();
var index = map[key];
if (index > effectIndex) {
effectIndex = index;
}
len = len > i - effectIndex ? len : i - effectIndex
map[key] = i
}
return len
};
// 方法二
var lengthOfLongestSubstring = function(s) {
var str = '';
var len = 0;
for (var i = 0; i < s.length; i++) {
var index = str.indexOf(s[i])
if (index > -1) {
str = str.slice(index + 1);
}
str += s[i];
len = len > str.length ? len : str.length
}
return len
};
2. Python
def lengthOfLongestSubstring(self, s: str) -> int:
# 声明字典，Python中要是用字典做这种查询，数组很慢
arr = {}
max_length = 0
effective_index = -1
for (index, char) in enumerate(s):
# 是否需要改变effective_index
if char in arr and arr[char] > effective_index:
effective_index = arr[char]
temp_length = index - effective_index
if temp_length > max_length:
max_length = temp_length
arr[char] = index
return max_length
# 执行用时 :
# 64 ms
# 在所有 Python3 提交中击败了
# 99.38%
# 的用户
# 可见python和java速度上不是一个重量级的对手
# 以后有时间 写上C的代码
