乐趣区

[LeetCode]无重复字符的最长子串(LongestSubstringWithoutRepeatingCharacters)

题目描述
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例:给定 “abcabcbb”,没有重复字符的最长子串是 “abc”,那么长度就是 3。给定 “bbbbb”,最长的子串就是 “b”,长度是 1。给定 “pwwkew”,最长子串是 “wke”,长度是 3。请注意答案必须是一个子串,”pwke” 是 子序列 而不是子串。
解决方法
使用 HashMap 记录字符上次出现的位置,用 pre 记录最近重复字符出现的位置,则 i(当前位置)-pre 就是当前字符最长无重复字符的长度,取最大的就是字符串的最长无重复字符的长度
public int lengthOfLongestSubstring(String str) {
if (str == null || str.length() < 1)
return 0;

// 记录字符上次出现的位置
HashMap<Character, Integer> map = new HashMap<>();
int max = 0;
// 最近出现重复字符的位置
int pre = -1;

for (int i = 0, strLen = str.length(); i < strLen; i++) {
Character ch = str.charAt(i);
Integer index = map.get(ch);
if (index != null)
pre = Math.max(pre, index);
max = Math.max(max, i – pre);
map.put(ch, i);
}

return max;
}
时间复杂度:O(n)
原文地址:https://lierabbit.cn/2018/04/…

退出移动版