文章目录如下
（1）自己的思路
（2）自己的代码
（3）别人的思路
（4）别人的代码
（5）对比自己的不足之处
题目如下：
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
Subscribe to see which companies asked this question
相对来说这道题比较简单，这得益于C++给我们实现了很多基本的数据结构，例如这道题中我们就用到了vector，自己写的代码在网站上没有通过测试，但是在自己的编译器（VS2015能够正确执行），本人在检查了代码之后，觉得逻辑没有什问题，因该是网站有一些bug。稍后贴出代码，还望各位网友指正~
（1）自己的思路
a.将原始字符串按照题目的要求进行分词（字串），然后保存每个字串的初始位置，这样的话每个字串的长度，就等于相邻两个字串初始位置的差。按照这种方法算出每个字串的长度，取出最长的长度返回即可。
b.在实现的过程中，有两个特例，●只有一个字符的字符串例如："x"；●空字符串例如"". 对于这两种情况我们无需进行a步骤的操作，直接返回长度1与长度0即可。
if (s == "") return 0; if (s.size() == 1) return 1;
c.当字符串的长度大于等于2时，我们依次两两比较原字符串相邻的两个字符，如果相同，则标认为相同的两个字符中，后一个为新字串的开始，记录后一个字符的位置为新字串的起始位置。其中s为原始字符串
char tmp1 = s.at(i); char tmp2 = s.at(i + 1); //只添加新子串起始位置 if (tmp1==tmp2) vector.push_back(i+1);
d.在字符串结尾的地方，我们要算上结束符' '，只有这样我们才能统计最后一个子串的长度，其中slen是原字符串的长度
if (i == slen - 2) { vector.push_back(slen); }
e.由于每个字串的起始位置都保存到了vector中，所以最后只需要将vector中相邻的元素相减，便可得到每个子串的长度，比较选出最大的即可。
for (int j = 1;j < vector.size(); j++) if (vector.at(j) - vector.at(j-1)>maxLen) maxLen = vector.at(j) - vector.at(j-1);
（2）自己的代码
#include<iostream> #include<string> #include<vector> using namespace std; class Solution { public: int lengthOfLongestSubstring(string s) { if (s == "") return 0; if (s.size() == 1) return 1; //所保存的是每一个子串的的开始位置 vector<int> vector(0); vector.push_back(0); int maxLen = 0; int slen = s.size(); int i; for (i = 0; i < slen-1; i++) { char tmp1 = s.at(i); char tmp2 = s.at(i + 1); //只添加新子串起始位置 if (tmp1==tmp2) vector.push_back(i+1); //要把原始字符串的结尾符' '包括在内 if (i == slen - 2) { vector.push_back(slen); } } for (int j = 1;j < vector.size(); j++) if (vector.at(j) - vector.at(j-1)>maxLen) maxLen = vector.at(j) - vector.at(j-1); return maxLen; } }; int main() { vector<int> v(0); string s("bdb"); Solution solution; int len = solution.lengthOfLongestSubstring(s); cout << len <<endl; return 0; }
（3）别人的思路
a.两个相同的字符之前的字符组合为一个子串（包括后一个相同的字符）
b.使用hash来判断字符是否相同
c.使用整形变量start来记录最长子串下一个邻接子串的起始位置
d.发现有更长的子串出现时，更新子串长度
（4）别人的代码
class Solution { public: int lengthOfLongestSubstring(string s) { int hash[256]; for (int i = 0; i<256; i++) hash[i] = -1; //start 只标注当前最长串的下一个子串的起始位置（当前最长串的结尾位置+1） int start = 0, ans = 0; int i; for (i = 0; i<s.size(); i++) { //发现相同的字符做以下处理 if (-1 != hash[s[i]]) { //发现下一个重复的字符时，计算当前重复字母的长度，并与之前出现过该字母的最长字串长度相比较，如果比最长长度大，变更新长度 if (ans < i - start) ans = i - start; //更新start的位置 if (hash[s[i]] + 1 > start) start = hash[s[i]] + 1; } hash[s[i]] = i; } //在结尾的时候，计算最后一个子串的长度，并与前面的最长串相比较 if (ans < i - start) ans = i - start; return ans; } };
（5）对比自己的不足之处
其实我觉得最主要的差别是我把题意给理解错了……我以为所谓的子串的定义是不能连续出现两个相同的字符，然而题目中的子串要求是不能出现相同的字符。
另外别人的答案里面对hash的应用确实让我眼前一亮，赞赞赞！