Longest Substring Without Repeating Characters (Medium)

問題描述

給出一個數(shù)組，求其連續(xù)不重復(fù)子數(shù)組最大長度，原代碼見 GitHub 17/05/25

Examples
Input
Given "abcabcbb",
Output
The answer is "abc", which the length is 3

算法思路

• 若碰到重復(fù)字符，要求達(dá)到目標(biāo)數(shù)組兩邊動態(tài)伸縮目的，需要設(shè)置兩個邊界變量

• 奔跑者 在前面奔跑，每次都把當(dāng)前字符存入 Set，若集合中已存在該字符，則停止奔跑

• 行走者 在后面行走，每次都把當(dāng)前字符移出 Set，若當(dāng)前字符與 奔跑者 當(dāng)前字符相同，則停止行走

通過以上算法，便可達(dá)到動態(tài)伸縮不重復(fù)子數(shù)組的目的，最大長度求解也變得相當(dāng)簡單

AC 代碼

int lengthOfLongestSubstring(string s) {set<char> set;int max = 0;int walker = 0, runner = 0;while (runner < s.size()) {char rc = s.at(runner);if (set.find(rc) != set.end()) {char wc;/*when two chars at walker and runner are equalswalker stops*/while ((wc = s.at(walker++)) != rc) {set.erase(wc);}} else {set.insert(rc);}if (max < runner - walker + 1) {max = runner - walker + 1;}runner++;}return max; }

總結(jié)

以上是生活随笔為你收集整理的子数组系列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。