LeetCode: 3 无重复字符的最长子串 (Java)

时间:2020-12-20 07:29:55

3. 无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

LeetCode: 3 无重复字符的最长子串 (Java)

最初始的解法方法就是遍历暴力每个元素,然后以那个元素为起始点,然后进行判断是否出现了重复元素,这样时间的复杂度就是O(n2),这样的时间复杂度有点高,基本上已经预定了时间超出限制。所以我们要用别的解法方法。 
那么比较好的解决方法就是用 双指针的思想,这题其实把握了思想还是挺简单的,要保证无重复的的,一般会先想到HashSet,可以保证数组的字符的唯一性。 
设置一左一右两个指针,每次我们都移动右指针,如果右边的指针中的元素在Set中存在了,那么就要开始根据已经存在的元素移动左边指针了。同时我们要把左右指针里面的元素所在的索引值(index)给保存下来。 
代码还是很好理解的:

show the code

 public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) return 0;
Set<Character> set = new HashSet<>();
LinkedList<Integer> list = new LinkedList<>();
char[] charsArray = s.toCharArray();
int left = 0;
int res = 0;
for (int right = 0, len = charsArray.length; right < len; ++right) {
if (set.contains(charsArray[right])) {
res = Math.max(res, right - left);
while (set.contains(charsArray[right])) {
int index = list.removeFirst();
set.remove(charsArray[index]);
}
list.addLast(right);
left = list.getFirst();
set.add(charsArray[right]);
} else if (right == len - 1) {
res = Math.max(res, right - left + 1);
} else {
set.add(charsArray[right]);
list.addLast(right);
}
}
return res;
}

时间复杂度O(n),空间复杂度O(n)。