题目描述
来源:Longest Substring Without Repeating Characters
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
算法分析
1. 暴力法
算法描述
需要一个变量记录当前子串长度,一个指针i记录当前子串开头,指针j遍历当前子串,哈希表记录当前子串是否存在重复字符
时间复杂度:O(n^3)
由于本题数据范围0 <= s.length <= 5 * 10^4
,所以n^3的时间复杂度会超时
2. 双指针法
算法解析
在暴力法的求解中,我们重复的遍历了一些字符,因此,应考虑对于以j为终点的最长无重复子串,它的起点i是不是和j同方向移动,即移动是否有同向性,是否单调,如果i和j不同向移动,随着j向右移动,i向左移动,则本题无法使用双指针
证明
1. 指针i1是以j1为结尾最长无重复子串的起点,当指针j1移动到j2位置
2. 利用反证法,假设i1向左移动,那么指针i2是以j2为结尾最长无重复子串的起点
3. 与指针i1是以j1为结尾最长无重复子串的起点假设矛盾,因此i和j的移动具有同向性即单调性
算法描述
快指针fast作为最长无重复子串的结尾,慢指针slow作为最长无重复子串的开头,哈希表记录slow到fast之间字符出现的次数,需要注意:
1. 如何记录slow到fast之间字符出现次数:
哈希表记录fast指针指向的字符次数,同时随着slow指针移动,更新相应指针指向字符的次数
2. 什么时候移动慢指针?
当哈希表记录到当前fast指针指向的字符次数大于等于2,则开始移动慢指针
3. 把慢指针移动到什么位置结束?
移动到当前fast指针指向的字符次数小于2,则慢指针移动结束
时间复杂度:O(n)
代码实现
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> record;
int n = s.size();
int result = 0;
for(int slow = 0, fast = 0; fast < n; fast ++) {
char c = s[fast];
record[c] ++;
while(record[c] >= 2) {
record[s[slow]] --;
slow ++;
}
result = max(result, fast - slow + 1);
}
return result;
}
};
总结
- 当使用双指针算法时,需要注意两指针移动是否有同向性即单调性
- 写代码时,注意思考慢指针何时移动,在何时停止移动