这个题目开始以为会有很多高级的方法,其实我用了一种我认为最简单的方法来解。
先说一下思路:
最开始可能是脑子秀逗了。
天真的认为:
从数组第一个元素开始枚举,如果后面的元素和“第一个”元素不一样,终止进入下一个循环,输出最大的sum。
显然不对啊!!!应该是后面的元素和前面的所有元素不一样。
WRONG一次
欧克,这种暴力的解法确实过了。不过首先它说的是字母,如果是英语字母算上大小写的话,应该是26*2个,所有的ascII字母256个,我开了一个300的数组应该够存了吧。
思路没问题但是还是WA了第二次,为啥???因为终止条件写的不够明显。如果到最后也没有重复的我都程序是会出错的。
第三WA是因为如果只有一个元素的时候程序会挂掉,简单题的边界问题很重要啊!!!!
最后pending了好久,我一直以为会超时,结果没有超时。
偶也~
其实,时间上还可以优化。
如果从x上开始找,i 和j的元素一样的话,下一次可以不从x+1上开始寻找而是可以从i+1上开始寻找。这样可以将时间维持在线性的扫描上,不过需要额外的存一下i和j的下标
class Solution { public: int lengthOfLongestSubstring(string s) { // Note: The Solution object is instantiated only once and is reused by each test case. int sum = 0; if(s.length() == 1) return 1; for(int i = 0; i < s.length();i++) { int flag[300]; for(int k = 0;k < 300;k++) { flag[k] = 0; } flag[s[i]] = 1; for(int j = i+1; j < s.length();j++) { if(flag[s[j]] == 1) { if(j - i > sum) sum = j - i; break; } if(j == s.length() - 1) { if(j - i + 1 > sum) sum = j - i + 1; break;<br /> } flag[s[j]] = 1; } } return sum; } };