T N T

美食博主

0%

#3 Longest Substring Without Repeating Characters

Posted on Edited on In

Description

Given a string, find the length of the longest substring without repeating characters.

Example1: 

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example2: 

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example3: 

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解法一 HashMap滑动窗口

思想：建立一个HashMap，反转索引和值，HashMap用来记录每个字符最后出现的位置，滑动窗口只需改变left指针即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
	public:
		int lengthOfLongestSubstring(string s){
			int res = 0,left = -1, n = s.size();
			unordered_map<int,int>m;
			for (int i=0; i<n; i++){
				if (m.count(s[i]) && m[s[i]] > left) {	// 字符出现过并且在滑动窗口之内
					left = m[s[i]]
				}
				m[s[i]] = i;
				res = max(res, i-left);
			}
			return res;
		}
};

解法二 向量数组滑动窗口

思想：与解法一思想相同，只不过将HashMap改为大小为128（键盘只能输入128种字符）的向量数组，初始化为-1，不用像HashMap 一样查找字符是否存在映射了，而是直接用数组种的值来更新left 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
	public:
		int lengthOfLongestSubstring(string s){
			vector<int> m(128,-1);
			int res = 0, left = -1, n = s.size();
			for (int i=0; i < n; i++){
				left = max(left, m[s[i]]);
				m[s[i]] = i;
				res = max(res, i-left);
			}
			return res;
		}
};

解法三 HashSet滑动窗口

思想：与解法一思想相同，只不过把出现过的字符都放入HashSet 中，遇到HashSet中没有出现的字符就加入HashSet中并更新res，如果遇到重复的，则从左边开始删除字符，直到删到重复的字符为止 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
	public:
		int lengthOfLongestSubstring(string s){
			int res = 0, left = 0; i = 0, n = s.size();
			unordered_set<char> t;
			while (i<n){
				if (!t.count(s[i])){
					t.insert(s[i++]);
					res = max(res, (int)t.size());
				} else {
					t.erase(s[left++]);
				}
			}
			return res;
		}
};