本文主要是介绍【LeetCode】4. Longest Substring Without Repeating Characters 最长无重复子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
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.
翻译：
找到最长无重复子串，返回长度。
思路：
打算在以后的博客中，写上自己的思路、贴上自己的代码的同时，也分析一下别人的思路和写法，毕竟自己的算法不一定是最优的。这道题在最开始做的时候，我的想法非常简单：
1.若给定字符串为空，返回0（注意边界情况）；否则转2。
2.用tempString来存储无重复子串,maxSize来记录最长无重复子串的长度；
初始化tempString为给定字符串的第一个字符，maxSize=1；
从字符串的第2个字符开始，到字符串结束，依次检测每一个字符是否出现在当前无重复子串中：
（1） 若这个字符在没有出现在当前无重复子串中，将该字符加入到当前无重复子串中；
（2）若这个字符出现在了当前无重复子串中，
比较该无重复子串的长度与maxSize的大小，若该无重复子串的长度大于maxSize，更新maxSize为该无重复子串的长度；
更新tempString为字符串中出现当前字符的下一个字符起始到该字符为止的子串（这里说的比较绕口，或不好懂，可以看代码）；
3.待整个字符串都检测完毕后，最后判断一次tempString的长度与maxSize的大小，返回较大的一个。
代码：
public class Solution {public int LengthOfLongestSubstring(string s) {if(s=="")return 0;char[] array=s.ToCharArray();string tempString=array[0].ToString();int maxSize=1;for(int i=1;i<array.Count();i++){int index=tempString.IndexOf(array[i]);if(index!=-1)//若在tempString中存在这个字符{if(tempString.Length>maxSize)maxSize=tempString.Length;tempString=tempString.Substring(index+1)+array[i].ToString();}else//若在tempString中不存在这个字符tempString+=array[i].ToString();}if(tempString.Length>maxSize)return tempString.Length;return maxSize;}
}在上面的代码中我应用了额外的空间，包括将字符串转换成字符数组，以及使用tempString来存储当前无重复子串，其实都是不必要的，下面这段代码我使用了C#中的
int string.IndexOf(char value, int startIndex, int count)函数来取代上面代码中应用到的int string.IndexOf(char value)来查找字符串中是否存在某个字符，于是不需要额外将字符串转化成字符数组，也不需要使用一个临时的string变量tempString来存储当前无重复子串。
我对上面的代码进行了稍微的修改，使用startIndex来记录当前无重复子串的起始位置，count记录当前无重复子串的长度，maxSize仍然记录最长无公共子串的长度。即用startIndex和count两个变量来记录无重复子串在原字符串中的起始位置和长度的方式来记录当前无重复子串，而不是单独使用一个变量。经过这样的改进后，空间上仅需要三个int类型，时间复杂度为O(n)，速度大大提升。
改进后的代码：
public class Solution {public int LengthOfLongestSubstring(string s) {if(s=="")return 0;int startIndex=0;int count=1;int maxSize=1;for(int i=1;i<s.Length;i++){int index=s.IndexOf(s[i],startIndex,count);//从字符串的startIndex下标开始，检测长度为count的子串中是否存在s[i]，若存在，则返回s[i]在这个字符串中的位置（下标）if(index!=-1)//当前无重复子串中存在这个字符{if(count>maxSize)maxSize=count;startIndex=index+1;//产生新的无重复子串，这个无重复子串从index下一个位置开始，到是s[i]结束count=i-index;//计算新的无重复子串的长度}else//将s[i]加入当前无重复子串中count++;}if(count>maxSize)return count;return maxSize;}
}
这篇关于【LeetCode】4. Longest Substring Without Repeating Characters 最长无重复子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
