[LeetCode刷题笔记]3 - 无重复字符的最长子串（哈希表 + 双指针）

一、题目描述

• 给定一个字符串，输出连续的不包含重复字符的子串的最长长度。
• 请注意子串和子序列的区别：
  • 子串一定是连续的一段；
  • 子序列不一定是连续的一段，但下标要求是递增的；

示例：

提示：

• $0<=s.length<=5\ast 10^4$
• $s$ 由英文字母、数字、符号和空格组成

二、求解思路：哈希表 + 双指针

思路

• 定义两个指针 $i,j(j<=i)$，表示当前扫描到的子串是 $[j,i]$ （闭区间）。
• 扫描过程中维护一个哈希表 unordered_map<char,int> h ，表示 $[j,i]$中每个字符出现的次数。
• 线性扫描的流程：
  • 指针 $i$ 向后不断移位遍历字符串每一位字符，同时将哈希表中 $s[i]$ 的计数加一;
  • 假设 $i$ 移动前的区间 $[j,i]$ 中没有重复字符，则 $i$ 移动后，只有 $s[i]$ 可能出现 2 次；
  • 此时，我们不断向后移动 $j$，直至区间 $[j,i]$中 $s[i]$ 的个数等于 1 为止，这样的区间才回再次满足题意；
  • 更新最长的子串长度；

C++代码

class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希表存储每个字符出现的次数
unordered_map<char, int> h;
int ans = 0;
// 最长无重复字符子串的长度，即存储输出结果
for (int i = 0, j = 0; i < s.size(); ++i) {
++h[s[i]];
// 把s[i]字符出现的次数加一
// 当s[i]字符出现次数大于1时，说明加入上一循环[j,i]区间达到最大，需要更新j
// 更新j：直到s[i]字符次数=1为止，此时的新区间会再次满足题意
while (j < i && h[s[i]] > 1) --h[s[j++]];
ans = max(ans, i - j + 1);
// 更新ans为最大值
}
return ans;
}
};

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

最后

以上就是落寞保温杯为你收集整理的[LeetCode刷题笔记]3 - 无重复字符的最长子串（哈希表 + 双指针）的全部内容，希望文章能够帮你解决[LeetCode刷题笔记]3 - 无重复字符的最长子串（哈希表 + 双指针）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。