首页 » 编程之美 » 正文

[leetcode_3]Longest Substring Without Repeating Characters

这个题目开始以为会有很多高级的方法,其实我用了一种我认为最简单的方法来解。
先说一下思路:
最开始可能是脑子秀逗了。
天真的认为:
从数组第一个元素开始枚举,如果后面的元素和“第一个”元素不一样,终止进入下一个循环,输出最大的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;
    }
};

发表评论