8000 Merge pull request #3 from hex108/master · slamke/leetcode@f68d5ce · GitHub
[go: up one dir, main page]

Skip to content

Commit f68d5ce

Browse files
committed
Merge pull request soulmachine#3 from hex108/master
an optimization for problem: 12.5 Longest Substring Without Repeating Charac...
2 parents 3513ef7 + 8e44cf8 commit f68d5ce

File tree

1 file changed

+8
-8
lines changed

1 file changed

+8
-8
lines changed

C++/chapGreedy.tex

+8-8
Original file line numberDiff line numberDiff line change
@@ -287,18 +287,18 @@ \subsubsection{代码}
287287
int lengthOfLongestSubstring(string s) {
288288
const int ASCII_MAX = 26;
289289
int last[ASCII_MAX]; // 记录字符上次出现过的位置
290+
int start = 0; // 记录当前子串的起始位置
291+
290292
fill(last, last + ASCII_MAX, -1); // 0也是有效位置,因此初始化为-1
291-
int len = 0, max_len = 0;
292-
for (size_t i = 0; i < s.size(); i++, len++) {
293-
if (last[s[i] - 'a'] >= 0) {
294-
max_len = max(len, max_len);
295-
len = 0;
296-
i = last[s[i] - 'a'] + 1;
297-
fill(last, last + ASCII_MAX, -1); // 重新开始
293+
int max_len = 0;
294+
for (int i = 0; i < s.size(); i++) {
295+
if (last[s[i] - 'a'] >= start) {
296+
max_len = max(i - start, max_len);
297+
start = last[s[i] - 'a'] + 1;
298298
}
299299
last[s[i] - 'a'] = i;
300300
}
301-
return max(len, max_len); // 别忘了最后一次,例如"abcd"
301+
return max((int)s.size() - start, max_len); // 别忘了最后一次,例如"abcd"
302302
}
303303
};
304304
\end{Code}

0 commit comments

Comments
 (0)
0