酒泉市住房和城乡建设局网站,wordpress标题重复,网站开发怎么实现用户一对一发文字图片,网上销售平台怎么做无重复字符的最长子串原题地址
方法一#xff1a;滑动窗口#xff08;双指针#xff09; 哈希集合
考虑找出字符串s的所有的无重复字符的子串#xff0c;求出这些子串长度的最大值即可。
使用下标 [left,right] 来维护子串。我们只需要找到每一个 left 对应的所有 righ…无重复字符的最长子串原题地址
方法一滑动窗口双指针 哈希集合
考虑找出字符串s的所有的无重复字符的子串求出这些子串长度的最大值即可。
使用下标 [left,right] 来维护子串。我们只需要找到每一个 left 对应的所有 right 即可换句话说固定了 left 之后我们让 right 从 left 的位置开始向后滑动直到 [left,right] 出现重复字符为止。
以下为所有无重复字符的子串
(a) b c a b c b b
(a b) c a b c b b
(a b c) a b c b b
a (b) c a b c b b
a (b c) a b c b b
a (b c a) b c b b
a b (c) a b c b b
a b (c a) b c b b
a b (c a b) c b b
a b c (a) b c b b
a b c (a b) c b b
a b c (a b c) b b
a b c a (b) c b b
a b c a (b c) b b
a b c a b (c) b b
a b c a b (c b) b
a b c a b c (b) b
a b c a b c b (b)
由于我们要找的是这些子串中最长的那个所以固定 left 后先让 right 右移至出现重复字符或者 right 移动到字符串的末尾再统计该子串的长度即 right-left1 求出其中的最大值即可。
需要统计如下子串的长度
(a b c) a b c b b
a (b c a) b c b b
a b (c a b) c b b
a b c (a b c) b b
a b c a (b c) b b
a b c a b (c b) b
a b c a b c (b) b
a b c a b c b (b)
显然当某条子串 [left,right] 的右端点 right 已经到达字符串的末尾时若 left 继续右移只会缩短子串长度所以此时无需继续统计。
为了判断子串是否已经出现重复字符可以利用哈希集合如 C 中的 unordered_setchar 来存储 [left,right] 中的所有字符当 right 右移时就把最右边的字符添加到哈希集合中当 left 右移时就把最左边的字符从哈希集合中删除。这样每次只需判断子串新增加的字符是否已经在哈希集合中出现过即可。
// 方法一滑动窗口
class Solution
{
public:int lengthOfLongestSubstring(string s){if (s.empty()){return 0;}unordered_setchar us;int ans 0;// [left,right] 表示子串int left 0, right 0;us.insert(s[0]);while (1){// 右指针右移直到出现重复字符while (right 1 s.size() !us.count(s[right 1])){us.insert(s[right]);}// 子串长度为 right-left1ans max(ans, right - left 1);// 右指针走到尾子串不可能更长if (right s.size() - 1){break;}// 左指针右移在哈希表中去掉最左边的字符us.erase(s[left]);}return ans;}
};
方法二对方法一的优化实现左指针 left 的快速跳转
方法一是固定 left 让 right 尽可能右移从而统计所有的 [left,right] 区间长度 right-left1 的最大值这样最坏情况下 left 会遍历完整个字符串。
考虑用 key-value 模型的哈希表如 C 中的 unordered_setchar, int 每次把 [0,right] 的字符及其对应下标都存进去。
我们用 right 遍历字符串若 right 右移后指向的字符在哈希表中出现过且最后出现的下标在 [left,right] 的范围内说明此时的子串 [left,right] 已经出现了重复字符此时 left 应该跳转到 s[right] 最后一次出现的位置的后面。
下面的例子中 right 本来指向 f 右移后指向 c left 就要从 a 直接跳转到第一个 c 后面否则 [left,right] 会出现重复字符。
(a b c d e f) c
a b c (d e f c)
每次 right 右移后都要把 s[right] 及对应的下标 right 都存储到哈希表中也就是把 s[right] 当前最后出现的位置存储到哈希表中。
// 方法二滑动窗口优化
class Solution
{
public:int lengthOfLongestSubstring(string s){if (s.size() 1){return s.size();}unordered_mapchar, int um;int ans 0;// [left,right] 表示子串int left 0, right 0;um[s[0]] 0;// 右指针右移直到出现重复字符while (right s.size()){auto it um.find(s[right]);// 出现重复字符if (it ! um.end()){// 左指针跳转到重复字符上一次出现的位置之后left max(left, it-second 1);}// 子串长度为 right-left1ans max(ans, right - left 1);um[s[right]] right;}return ans;}
};
