本文主要是介绍leetcode_无重复字符的最长子串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、题目描述

 二、思路代码

     首先有一个需要我们注意，就是其中的符号不仅仅包括字母，还包括符号，数字，空格，我在程序里面检验发现最常为95个字符。

     这个我感觉需要用滑动窗口做，即不断移动开始点和末尾点，然后不断检验。

     代码如下：

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         //最长子串的长度
 5         int max_length=0;
 6         //如果s为空，返回0
 7         if (s=="")
 8             return max_length;
 9         //字符串s的长度
10         int length = s.size();
11         //从0位置开始搜索
12         //开始和结束位置
13         int start_loc = 0;
14         int end_loc = 0;
15         //记录两个重叠位置
16         int appear_first = -1;
17         int appear_second = 0;
18         for (int i=appear_first+1; i<length-max_length; i++)
19         {
20             if (i<appear_first+1)
21                 i = appear_first+1;
22             appear_first = i;
23             //当前开始与结束位置
24             start_loc = i;
25             end_loc = appear_second+1;
26             //只查看前95个字符
27             int j_max = min(length, i+95);
28             //判断以i为起点位置的无重复字符的子串，检验的时候j从重叠位置以后开始检验
29             for(int j=max(i+1, appear_second+1); j<j_max; j++)
30             {
31                 //appear_second设置为i+1
32                 appear_second = j;
33                 int count_num = 0;
34                 //对位置在s[j]的字符，检查其是否与前面s[start_loc:end_loc]的字符串重叠
35                 for(int k=start_loc; k<end_loc; k++)
36                 {
37                     if (s[j] != s[k])
38                         count_num++;
39                     else
40                         {
41                             //记录第一次出现位置
42                             appear_first = k;
43                             break;
44                         }
45                 }
46                 if (count_num == end_loc- start_loc)
47                     end_loc = appear_second+1;
48                 else
49                     break;
50             }
51             //更新max_length
52             max_length = max(max_length, end_loc-start_loc);
53         }
54         return max_length;
55     }
56 };

三、参考代码

别人给出的参考代码如下（C++版本）

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         if(s.size() == 0) return 0;
 5         unordered_set<char> lookup;
 6         int maxStr = 0;
 7         int left = 0;
 8         for(int i = 0; i < s.size(); i++){
 9             while (lookup.find(s[i]) != lookup.end()){
10                 lookup.erase(s[left]);
11                 left ++;
12             }
13             maxStr = max(maxStr,i-left+1);
14             lookup.insert(s[i]);
15     }
16         return maxStr;
17         
18     }
19 };

    可以看到代码精简了很多，而且最重要的是unordered_set这个数据类型的使用，是一种哈希无序哈希容器。

   这种数据结构使用让原本需要我在代码中自己实现的逐个判断的部分，变成这个容器自动实现了，所以实现了功能上的简化，这个是我需要进行借鉴的部分，并且这个容器通过哈希查找的话，速度会快很多。

   而且利用了unordered_set实现了滑动窗口的功能。

这篇关于leetcode_无重复字符的最长子串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！