该文已加入开源项目:LeetCodeAnimation(用动画的形式呈现解LeetCode题目的思路,目前 4000 Star )。地址:https://github.com/MisterBooo/LeetCodeAnimation
LeetCode上第 3 号问题:Longest Substring Without Repeating Characters。
给定一个字符串,找出不含有重复字符的最长子串的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 无重复字符的最长子串是 "abc",其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1. 解释: 无重复字符的最长子串是 "b",其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 无重复字符的最长子串是 "wke",其长度为 3。 请注意,答案必须是一个子串,"pwke" 是一个子序列 而不是子串。
建立一个256位大小的整型数组freg,用来建立字符和其出现位置之间的映射。
维护一个滑动窗口,窗口内的都是没有重复的字符,去尽可能的扩大窗口的大小,窗口不停的向右滑动。
1// 3. Longest Substring Without Repeating Characters
2// https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
3//
4// 滑动窗口
5// 时间复杂度: O(len(s))
6// 空间复杂度: O(len(charset))
7class Solution {
8public:
9 int lengthOfLongestSubstring(string s) {
10 int freq[256] = {0};
11 int l = 0, r = -1; //滑动窗口为s[l...r]
12 int res = 0;
13 // 整个循环从 l == 0; r == -1 这个空窗口开始
14 // 到l == s.size(); r == s.size()-1 这个空窗口截止
15 // 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
16 while(l < s.size()){
17 if(r + 1 < s.size() && freq[s[r+1]] == 0){
18 r++;
19 freq[s[r]]++;
20 }else { //r已经到头 || freq[s[r+1]] == 1
21 freq[s[l]]--;
22 l++;
23 }
24 res = max(res, r-l+1);
25 }
26 return res;
27 }
28};