每日一练：无重复字符的最长字串

本文主要是介绍每日一练：无重复字符的最长字串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目要求

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 

子串

 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

二、解法1-set记录所有不重复字串 O(N^2)

遍历字符串，以每一个字符作为一次起点，遇见重复字符就更新最大长度，然后进入下一个循环

class Solution {
public:int lengthOfLongestSubstring(string s) {int first = 0,end = 0;int ret = 0;unordered_set<char> set;for(int i = 0;i < s.size();i++){set.clear();set.insert(s[i]);for(int j = i+1;j < s.size();j++){if(set.count(s[j]) != 0) // 存在{break;}else{set.insert(s[j]);}}if(set.size() > ret) // 更新最大长度ret = set.size();}return ret;}
};

       

三、解法2-滑动窗口 O(N)

这种方式是解法1的优化版，它优化了不必要的起点字符：

   按照解法1，如上图所示：当 a 作为起点时，遇到 d-d 就结束了，然后会让 b 作为起点，也是遇到 d-d 结束，但是在结束条件不变的情况下 b 一定比 a 小，此时应该跳过中间的字符，直接从第一个 d 的后一个字符为起点计算长度。

        解法2的流程如下：

        （1）没有遇见重复字符，记录当前字符的下一位，更新最大长度（right-left+1）

        （2）遇见重复字符，更新 left 到第一个重复字符的下一位，更新最大长度，更新当前字符的下一位，重复步骤（1）

class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> v(128, 0);int right = 0;int left = 0;int ret = 0;for(;right < s.size();right++){if(v[s[right]] == 0) // 无重复{v[s[right]] = right+1; // 记录当前字符的下一个位置ret = max(ret,right-left+1); // 更新最大长度}else // 有重复{left = max(left,v[s[right]]); // 更新leftret = max(ret,right-left+1);  // 更新最大长度v[s[right]] = right+1; // 更新当前字符的下一个位置}}return ret;}
};

这篇关于每日一练：无重复字符的最长字串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---