相同的測試用例，本地運行72ms，LeetCode上卻TLE，可能有哪些原因？

題目鏈接：Longest Substring Without Repeating Characters

語言是C#，代碼中使用了HashSet，是否可能是Mono的HashSet版本性能太差所導致的？

代碼：

public static int LengthOfLongestSubstring(string s)
{
if (s.Length &<= 1) { return s.Length; } int length = 0; for (int i = 0; i &< s.Length; i++) { HashSet& set = new HashSet&();
for (int j = 0; i + j &< s.Length; j++) { int offset = 0; if ((offset = Add(set, s[i + j])) != -1) { length = length &> j ? length : j;
i += offset;
break;
}
}
}
return length;
}

public static int Add(HashSet& set, char ch)
{
if (!set.Add(ch))
{
for (int i = 0; i &< set.Count; i++) { if (set.ElementAt(i) == ch) { return i + 1; } } } return -1; }

測試用例過長（長度3W的字元串）就不放了

本機運行截圖：

---

首先說結論：不是。因為我給了一個只用一個數組的O(n)的解法，仍然TLE了。下面我貼的是能accept的答案，然後注意如果你把數組的長度從256改成65536，它就TLE了。天知道到底發生了什麼。根據Mono的進展，我只能說leetcode用的可能是三千年前的Mono，從不更新。

通常來講刷leetcode我建議使用C語言，畢竟你是為了去面試，面試通常都是用C語言的，什麼垃圾數據結構都沒有，malloc了之後也不需要free，充分鍛煉打字速度。

而且leetcode計算速度的方法也十分詭異。通一份代碼我不斷地resubmit，可以看見他在90%和40%中間來回跳。

public class Solution {
public int LengthOfLongestSubstring(string s) {
var x = new bool[256];
var result = 0;
var current = 0;
var stringLength = s.Length;
for (int i = 0; i &< stringLength; i++) { int code = (int)s[i]; if (x[code]) { var newCurrent = i; while ((int)s[newCurrent - 1] != code) { newCurrent--; } for (int j = current; j &< newCurrent; j++) { x[(int)s[j]] = false; } current = newCurrent; } else { var length = i - current + 1; if (result &< length) { result = length; } } x[code] = true; } return result; } }

---

順手貼一個可以過的解法，和其它答案一樣需要用一個數組代替HashSet：

public class Solution {
public int LengthOfLongestSubstring(string s) {
var max = 0;
var lastSeen = new int[256];
var lastPairStart = -1;
for (int i = 0; i &< lastSeen.Length; i++) lastSeen[i] = -1; for (int i = 0; i &< s.Length; i++) { var c = s[i]; var pairLen = i - lastSeen[c]; var seqLen = i - lastPairStart; max = Math.Max(max, Math.Min(seqLen, pairLen)); lastPairStart = Math.Max(lastSeen[c], lastPairStart); lastSeen[c] = i; } return max; } }

---

C++我也TLE過。

leetcode TLE

本地測試msvc gcc均debug編譯時TLE

release並關優化（僅開inline）均秒return。

鬼知道leetcode上面是什麼奇葩編譯選項

---

用C++寫，動態規劃，順利AC：

Runtime: 216 ms.

Your runtime beats 20.20% of cppsubmissions.

class Solution {
public:
string longestPalindrome(string s) {
const int len = s.size();
if(len &<= 1) return s; bool dp[len][len]; //dp[i][j]表示s[i..j]是否是迴文 memset(dp, 0, sizeof(dp)); int resLeft = 0, resRight = 0; dp[0][0] = true; for(int i = 1; i &< len; i++) { dp[i][i] = true; dp[i][i-1] = true; //這個初始化容易忽略，當k=2時要用到 } for(int k = 2; k &<= len; k++) //枚舉子串長度 for(int i = 0; i &<= len-k; i++) //枚舉子串起始位置 { if(s[i] == s[i+k-1] dp[i+1][i+k-2]) { dp[i][i+k-1] = true; if(resRight-resLeft+1 &< k) { resLeft = i; resRight = i+k-1; } } } return s.substr(resLeft, resRight-resLeft+1); } };

---

可能為了卡你的HashSet故意加了點稀奇古怪的東西減速了吧，可以自己實現一個試試。

就像有些OJ沒開優化，STL怎麼用怎麼T，手寫一個相同複雜度的類似數據結構就快得飛起。

也可以聽輪子哥說的轉C語言，沒現成可用的數據結構你就會少很多這種困擾，逼你手寫。

說回這道題，其實O(n)就行，卡得也不算冤。

public class Solution
{
public int LengthOfLongestSubstring(string s)
{
int[] vis = new int[256];
for (int i = 0; i &< 256; ++i) { vis[i] = -1; } int p1 = 0, ans = 0, len = s.Length; for (int p2 = 0; p2 &< len; ++p2) { if (vis[s[p2]] != -1) { ans = Math.Max(ans, p2 - p1); for (; p1 &<= vis[s[p2]]; ++p1) { vis[s[p1]] = -1; } } vis[s[p2]] = p2; } return Math.Max(ans, len - p1); } };

---

我來噴輪子了。一個詞：誤人子弟。（題主居然還信了，真同情）

第一，@vczh給的code由於內層循環方向錯誤（從右往左掃）使得複雜度變為了256*n。

第二，題主的（期望）複雜度其實是256*n而不是什麼n^3。輪子說HashSet worst case的結論倒沒錯，不過這裡不是看最壞情況的時候。輪子是在五十步笑百步。（心疼輪子評論區被誤導的朋友們）

其他幾位答主@周擎宇和@薛訥訥給出的O（n）做法應該都是挺對的，題主可以參考。（另外，@Bravo Yeung您真的看題了嗎）

所以結論是：由於HashSet巨大的常數和複雜度的小問題共同導致超時。

---

推薦閱讀：