那家网站做的效果好,安徽建设工程信息网查工程师询平台,应用软件有哪些系统,网站cms是什么意思一.题目描述
无重复字符的最长子串 二.思路分析
题目要求我们找符合要求的最长子串#xff0c;要求是不能包含重复字符
确定一个子串只需确定它的左右区间即可#xff0c;于是我们可以两层循环暴力枚举所有的子串#xff0c;找到符合要求的#xff0c;并通过比较得到最长…一.题目描述
无重复字符的最长子串 二.思路分析
题目要求我们找符合要求的最长子串要求是不能包含重复字符
确定一个子串只需确定它的左右区间即可于是我们可以两层循环暴力枚举所有的子串找到符合要求的并通过比较得到最长的长度。还有一个问题怎么确定有没有重复字符呢可以使用哈希表,如果把字符丢进哈希表后没有重复那么right继续向后枚举如果重复了直接退出循环后面的不用枚举了肯定也会重复。
class Solution {
public:int lengthOfLongestSubstring(string s) {int n s.size();int ret 0;for (int left 0; left n; left){int hash[128] {0};for (int right left; right n; right){int in s[right];hash[in];if (hash[in] 1)//出现重复的字符了{break;}//没有出现重复字符ret max(ret, right - left 1);}}return ret;}
};
两层for循环时间复杂度是O(n^2)leetcode上面不会超时能通过。但用暴力枚举太浪费这道题了可以使用滑动窗口优化。
要想使用滑动窗口必须证明left和right都只会向前移动。 left固定在第一个位置right不断向后移动移动过程中如果没有出现重复字符则不断更新结果。当right移动到如图所示位置时出现了重复字符故left位置已经枚举完毕。 按照暴力枚举方法left向前移动一步right回退到left位置。但是最终right还是会走到原先标记的位置。因为经过上一轮枚举[left - 1, tmp)区间内都是没有重复字符的所以right会一直往前走。 所以right不必退回来保持在原地不动让left向右移动即可。我们发现此时区间内没有重复元素了所以要更新结果right继续向后移动。接下来的步骤就和前面的一样了。但是这里的left向后移动一步刚好就跳过了那个重复的元素接下来我们看一个不一样的例子 这里区间内出现重复元素left向后移动一步 但此时还是有重复元素此时right也没有必要向后枚举了因为肯定也是重复的。所以left还要继续向后移动直到跳过重复的字符wright才能被解放继续向后移动。故left可能向后移动多步这是一个循环的过程。 三.代码编写 根据滑动窗口的代码模版我们只需确定以上几个具体的步骤。那么什么时候更新结果呢当我们找到符合要求的子串是就更新,什么时候是符合要求的呢
当判断条件不成立
或者判断条件成立但通过不断地出窗口最终使判断条件不成立时是符合要求的。所以更新结果应该放在整个循环的最后。
class Solution {
public:int lengthOfLongestSubstring(string s) {int n s.size();int ret 0;int hash[128] {0};int left 0, right 0;while (right n){//进窗口int in s[right];hash[in];//判断while (hash[in] 1){//出窗口int out s[left];hash[out]--;left;}//更新结果ret max(ret, right - left 1);right;}return ret;}
};
时间复杂度O(n),效率大大提升
