无重复字符的最长字串（3）

题目

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例

输入: "abcabcbb" 输出: 3

输入: "bbbbb" 输出: 1

输入: "pwwkew" 输出: 3

算法

双指针 + 哈希表

左指针依次遍历每个字符，作为当前字串的起始位置 右指针从当前左指针开始向前移动，直到找到重复的字符时返回两指针之间的字串[l,r)的长度

export const lengthOfLongestSubstring = (s) => {
	let max = 0;
	for (let i = 0; i < s.length; i++) {
		let hashSet = new Set();
		let j = i;
		for (; j < s.length; j++) {
			if (hashSet.has(s[j])) {
				break;
			}
			hashSet.add(s[j]);
		}
		if (max < j - i) {
			max = j - i;
		}
	}
	return max;
};

优化双指针 + 哈希表

当右指针找到第r个位置有重复元素时，说明左指针l位置到r-1之间是没有重复元素的，所以此时不用移动右指针，只移动左指针直到找到重复元素（比如位置r1）并从哈希表中删除后，将左指针指向这个元素的后一个位置r1+1，此时从r1+1到r之间无重复元素继续移动右指针

不应让右指针移动到大于字符串长度的位置

export const lengthOfLongestSubstring = (s) => {
	const hashSet = new Set();
	let l = 0,
		r = -1;
	let max = 0;
	while (l < s.length) {
		if (l !== 0) {
			hashSet.delete(s.charAt(l - 1));
		}
		while (r < s.length - 1 && !hashSet.has(s.charAt(r + 1))) {
			hashSet.add(s.charAt(r + 1));
			r++;
		}
		max = Math.max(max, r - l + 1);
		l++;
	}
	return max;
};

使用map数据结构

使用map结构保存{字符：最后依次出现的位置}，使用一个指针l保存字串开始s[l]，使用一个指针遍历字符串指向字串结尾s[r]

export const lengthOfLongestSubstring = (s) => {
	const map = new Map();
	let l = 0,
		r = 0;
	let max = 0;
	for (; r < s.length; r++) {
		if (map.has(s[r])) {
			// 为了使左指针不向左移动，应取map中对应位置和l当前位置的较大值
			l = Math.max(map.get(s[r]) + 1, l);
		}
		map.set(s[r], r);
		max = Math.max(max, r - l + 1);
	}
	return max;
};