【LeetCode】3-Longest-Substring-Without-Repeating-Characters

此题第一次一遍AC。

题目要求

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

思路

两个指针,一个表示,一个表示
再用一个哈希表存储这两头中间的字符,可以有两种不同的记法:

  • <char, int> 表示当前串中有的char对应的position
  • <char, bool> 表示当前串中存在的char
    当然不一定需要使用map,用个array可以加快点效率,毕竟这里测试的char可以直接对应0~255。

然后大循环中每次往前移动一格,并判断新增的一个char是否在保存的表中,如果是的话就将往前移直到找到了新加的char
注意每次移动记得更新表中的数据。

实现

class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char, int> hash_map;
int total_length = s.size();
int max_length = 0;
int temp_length = 0;
int find_pos = 0;
int right_pos = 0;
int left_pos = 0;
for (; right_pos < total_length; right_pos++) {
if (hash_map.find(s[right_pos]) != hash_map.end()) {
find_pos = hash_map.find(s[right_pos])->second;
while(left_pos <= find_pos) {
hash_map.erase(hash_map.find(s[left_pos]));
left_pos++;
}
}
hash_map.insert(make_pair(s[right_pos], right_pos));
temp_length = right_pos - left_pos + 1;
max_length = max(max_length, temp_length);
}
return max_length;
}
};

这里效率较低用了122ms,如果用array的话肯定会快点。

坚持原创技术分享,您的支持将鼓励我继续创作!