LeetCode Problem 3: Longest Substring Without Repeating Characters
LeetCode Problem 3: Longest Substring Without Repeating Characters
LeetCode Problem 3: Longest Substring Without Repeating Characters
Question:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.Solution:
首先我第一反应想到了时间复杂度 O(n^3) 的方法，但是写出来之后有一些错误。另外后来又看Solution，说用了 O(n^3) 的方法，就会运行超时，不能通过。 后来看了第二个思路，感觉还是很容易理解，而且很有效的。主要思想就是滑动窗口。利用滑动窗口，可以将时间复杂度降低到 O(1)。
问题主要是要求我们找到一个字符串中，没有重复字符的最长子串。也就是说，最长的子串肯定不能存在相同的两个字符。 滑动窗口的思想，就是设定左、右边界，边界内即为我们的滑动窗口。设定一个 HashSet，用于记录滑动过程中右边界经过的字符。 滑动的策略是，我们判断右边界所在位置的字符是否存在于 HashSet 中。如果存在，说明之前存在重复的字符串，此时向右滑动左边界，并移除 HashSet 中的该字符；如果不存在，说明在滑动过程中还没有遇到（或者 HashSet 中相关记录已经删除）该字符，那么将该字符记录到 HashSet 中，同时比较此时左右边界长度与当前记录的最大字符串长度，取两者最大值。
Java 代码如下：
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int length = s.length();
int left = 0, right = 0;
HashSet<Character> hashSet = new HashSet<>();
while(left < length && right < length){
if (hashSet.contains(s.charAt(right))){
hashSet.remove(s.charAt(left++));
}else{
hashSet.add(s.charAt(right++));
maxLength = Math.max(maxLength, right - left);
}
}
return maxLength;
}笔者按照这种思路仿写了 C++ 的算法：
#include <hash_set>
using namespace stdext;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 统计最大长度
int maxLength = 0;
// 原字符串长度
int len = s.length();
// 设定左右边界
int left = 0, right = 0;
// 记录已出现字符的 Hash Set
hash_set<char> set;
while(left < len && right < len) {
// 查找右边界的元素是否在 Hash Set 中出现
// 如果找到，则左边界右移
if(set.find(s[right]) != set.end() ) {
set.erase(set.find(s[right++]));
left++;
}
// 如果没找到，则将右边界所在字符添加进入 Hash Set，并更新最大长度
else {
set.insert(s[right++]);
maxLength = maxLength > (right - left) ? maxLength : (right - left);
}
}
return maxLength;
}
};尴尬的是，LeetCode 好像不让我加入 HashSet 相关头文件…… 所以还是改了方法，用 unordered_map。而且方法改变之后，思路更加简单。用 map 存储 (char, int) 数据对，其中 char 存储字符，int 存储在滑动窗口遍历过程中的该字符在最右位置。以右边界为遍历对象，遍历过程中持续更新当前字符对应的最右位置。如果在 map 中找到了当前字符，则更新该字符最右位置。
例如有字符串 abcdabde1234：右边界遍历前 4 个字符时，map 中存储的 ‘a’ 的对应 int 值为 0 （即第一个 ‘a’ 值的位置）；当右边界遍历到第 5 个字符时，遍历 map 发现 map 中存在 ‘a’ 的关键字，这时候将对应 int 值由 0 改为 4，而且更新左边界为 4+1 （因为前面的字符串已经出现重复，所以从当前右边界 + 1 的位置重新统计即可）。
C++ 代码如下（已通过 LeetCode 检验）：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 统计最大长度
int maxLength = 0;
// 原字符串长度
int len = s.length();
// 设定左右边界
int left = 0, right = 0;
// 记录已出现字符以及最右位置的 map
unordered_map<char, int> map;
for(; right < len; ++right) {
// 查找右边界的元素是否在 Hash Set 中出现
// 如果找到，则左边界右移
if(map.find(s[right]) != map.end() ) {
left = map.find(s[right])->second + 1 > left ? map.find(s[right])->second + 1 : left ;
}
// 比较并更新最大长度
maxLength = maxLength > (right - left + 1) ? maxLength : (right - left + 1);
// 更新 Key 值
map[s[right]] = right;
}
return maxLength;
}
};