leetcode3

约定不等于承诺〃 2022-08-08 17:59 85阅读 0赞

Longest SubString Without Repeating Characters

中文翻译，最长无重复字符的子串，返回其长度。

最开始的思路就是两重循环。

第一层循环决定子串的起始点，从0开始。

第二层循环开始依次往后比较，此处维护一个map数组，如果当前字符存在（不重复），则表示无重复子串的长度+1

否则，终止二层循环。

每一次大循环结束前对计数进行比较，记录最大值。

每一次循环开始前，要清空map数组重新计数。

代码：

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
    		unsigned int i;
    		unsigned int j;
    		int count=0;
    		int max = 0;
    		int map[256]={0};
    		for(i=0;i<s.length();i++)
    		{
    			count =0;
    			memset(map,0,sizeof(map));
    			for(j=i;j<s.length();j++)
    			{
    				if(map[s[j]-' ']==0)
    				{
    					map[s[j]-' ']=1;
    					count ++;
    				}
    				else
    				{
    					break;
    				}
    			}
    			if(max < count)
    				max = count;
    		}
    		return max;
    	}
    };

上述方式可以通过，但是效率不高。

提交后在网上看到另一种比较高效地方式，在此分享。参考：http://www.cnblogs.com/mickole/p/3698956.html

其思路是维护两个索引i和j。

i不停的往前走，直到走到s\[i\] == s\[j\] 此处依然使用map数组来标记某字符是否在子串中出现。

而当s\[i\] == s\[j\]时，此时必然出现无重复子串，记录当前长度。

j向前滑动到与s\[i\]相同的位置进行下一次子串的判断。

最后值得注意的是：

count = max (count , (int )(s.length()-1 )) 是将串尾部不重复的子串加入比较。例如 "aab"的情况

代码：

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
    		int map[256]={0};
    		unsigned int i;
    		unsigned int j=0;
    		int count=0;
    		for(i=0;i<s.length();i++)
    		{
    		//	memset(map,0,sizeof(map));
    			if(map[s[i]-' ']==0)
    				map[s[i]-' ']=1;
    			else
    			{
    				count = max(count,(int)(i-j));
    				//memset(map,0,sizeof(map));
    				while(s[j]!=s[i])
    				{
    					map[s[j]-' ']=0;
    					//memset(map,0,sizeof(map));
    					j++;
    				}
    				j++;
    			}//考虑重复情况
    		}
    		count = max(count,(int)(s.length()-j));//考虑不重复情况类似abcd
    		return count;
    	}
    };