子数组系列

Longest Substring Without Repeating Characters (Medium)

问题描述

给出一个数组，求其连续不重复子数组最大长度，原代码见 GitHub 17/05/25

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

算法思路

• 若碰到重复字符，要求达到目标数组两边动态伸缩目的，需要设置两个边界变量

• 奔跑者 在前面奔跑，每次都把当前字符存入 Set，若集合中已存在该字符，则停止奔跑

• 行走者 在后面行走，每次都把当前字符移出 Set，若当前字符与 奔跑者 当前字符相同，则停止行走

通过以上算法，便可达到动态伸缩不重复子数组的目的，最大长度求解也变得相当简单

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; }

总结

以上是生活随笔为你收集整理的子数组系列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。