题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解法1:滑动窗口
滑动窗口是解决字符串和数组类问题的一个重要工具。就本地而言,我们使用如下解题思路:
- 假设输入字符串为:pwwkew
- 初始化map, key为字符,value为该字符在输入字符串中的位置。
- 初始化i=0,j=0。
- 查看j所对应的元素newJValue是否否在与map中:
- 如果它在map中,则从map中删除i所指向的元素,并将i向右滑动,继续执行4。
- 如果它不在map中,则将其插入到map,并将j向右滑动,继续执行4。并起来当前最大值m。
class Solution {
public:
int lengthOfLongestSubstring(string str) {
int i = 0;
int j = 0;
int m = 0;
int size = (int)str.size();
map<char, int> tmap;
while (i<size && j<size) {
if (tmap.find(str[j]) == tmap.end()) {
tmap.insert(pair<char, int>(str[j], j));
j++;
m = max(m, j-i);
} else {
tmap.erase(tmap.find(str[i]));
i++;
}
}
return m;
}
};
复制代码
优化代码
这里的优化思路是:当i需要向右滑动的时候不需要一次一次的滑动,而是直接跳到新的重复元素。
举例来说,对于测试用例:pwwkew来讲。
当j=2,i=0是,map中已经有了pw了,对于j=2的w在map中已经存在w,所以此时需要将i右滑两次,只是我们可以直接将i跳到2,而不用一步一步的滑动。具体代码如下:
int lengthOfLongestSubstring(string str) {
int i = 0;
int j = 0;
int m = 0;
int size = (int)str.size();
map<char, int> tmap;
while (j<size) {
if (tmap.find(str[j]) != tmap.end()) {
i = max(tmap.find(str[j])->second, i);
}
m = max(m, j-i+1);
tmap[str[j]] = j+1;
j++;
}
return m;
}
复制代码