leetcode Longest Substring Without Repeating Characters

PS1：我想到一个好的方法去实现下面说的那个find函数，而且确定是常数时间：

对这个题目我的思想是从第一个字符往后找，知道找到在之前字符串中有出现的字符，这样的话，从出现的那个位置后的一个位置开始继续新的查找。现在有一个问题就是s.find（）这个函数的时间复杂度是O(1)还是O(n)如果是O(1)的话那我这个算法就是O(n)的时间复杂度，如果是O(n)的话那就是O(n2)了。

代码：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int lengthOfLongestSubString(string s)
 6 {
 7     if (s.length() == 0)
 8         return 0;
 9     int max = 1;
10     int j = 0;
11     for (int i = 1; i < s.length(); i++)
12     {
13         int t = s.find(s[i], j);
14         if (t == i)
15         {
16             int temp = i - j + 1;
17             if (temp > max)
18                 max = temp;
19         }
20         else if (t < i)
21         {
22             j = t + 1;
23         }
24     }
25     return max;
26 }
27 
28 int main()
29 {
30     string s = "abcabcbb";
31     cout << lengthOfLongestSubString(s) << endl;
32 }

这个题其实我写的是不好的，但我不知道在leetcode上看到的那个结局问题用的时间上，我竟然是Cpp里面比较好的，挺神奇的一定是那个find特别效果特别好，要不然就是测试数据不是很厉害。

更好的代码：

 1 int lengthOfLongestSubstring(string s) {
 2   int n = s.length();
 3   int i = 0, j = 0;
 4   int maxLen = 0;
 5   bool exist[256] = { false };
 6   while (j < n) {
 7     if (exist[s[j]]) {
 8       maxLen = max(maxLen, j-i);
 9       while (s[i] != s[j]) {
10         exist[s[i]] = false;
11         i++;
12       }
13       i++;
14       j++;
15     } else {
16       exist[s[j]] = true;
17       j++;
18     }
19   }
20   maxLen = max(maxLen, n-i);
21   return maxLen;
22 }

这里就是用到了一个数据先暂存已经出现的字母，但是虽然他没有用find函数，但是由于里层的while循环同样可以做到找到已出现的并且循环后的i就是那个位置。这是一个好的代码。

我提交了一下这个代码发现和我的代码时间消耗几乎是一样的。费解！