[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 的下标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


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;
                }
                flag[s[j]] = 1;
            }
        }
        return sum;
    }
};