Leetcode刷题笔记—3. Longest Substring Without Repeating Characters

一、问题

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。(本题区分大小写字母)

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

二、解决

思路1:滑动窗口中做记录:

1)首先声明索引i和j 分别指向数组首尾,如果s[i j]中无重复字母,则将j 向后移动,直到j 要移动到的下一个字母(j+1未包括进数组s)与s[i j]中某一字母重复。此时j不能继续扩展了记录此时s[i j]的长度。

Leetcode刷题笔记—3. Longest Substring Without Repeating Characters

 

 Leetcode刷题笔记—3. Longest Substring Without Repeating Characters

Leetcode刷题笔记—3. Longest Substring Without Repeating Characters

 

 

2)然后将i 向后移动,直到抛出上述的重复字母时,j可以向后移动一位将重复字母包括进来。此时获得了新的s[i j]。

 

 

Leetcode刷题笔记—3. Longest Substring Without Repeating Characters

Leetcode刷题笔记—3. Longest Substring Without Repeating Characters

3)然后继续移动j 重复 1)2)的步骤,以此类推。

如何记录重复字符(如何判断j+1位置的字母是否重复):设置个数组freq[256] 有256个位置,如果freq为0 则说明没有重复。为1则说明产生了一个重复字符。

c++代码

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         int freq[256]={0}; //256个位置上的元素都为0,重复一次对应位置变为1
 5         int l=0,r=-1;
 6         int res=0; //记录满足条件子串的长度。
 7         
 8         while(l<s.size()){
 9             
10             if(r+1<s.size()&&freq[s[r+1]]==0){// 右边界之后的元素是否为重复元素,
11                 r++;   //不是则右边界可以继续扩展,右边界向后移动一位。
12                 freq[s[r]]++; // 将移动后的r位置重复频率更新一下。
13             }
14             else{   // 否则右边界无法扩展,
15                 freq[s[l]]--; //将l位置重复频率更新一下。
16                 l++; //则左边界向后移动一位。
17             }
18             res=max(res,r-l+1);  // 将当前取到的新子串与之前的子串进行比较,取长度最大的子串。
19         }
20         return res; // 最后循环结束后会获得一个最大的子串res
21     }
22 };

 

 

 

 

 

 

 

 

 

代码参考:https://github.com/liuyubobobo/Play-Leetcode

上一篇:[并查集] leetcode 128 Longest Consecutive Sequence


下一篇:Longest Common Prefix