Leetcode算法系列| 3. 无重复字符的最长子串
目录
- 1.题目
- 2.题解
- C# 解法一：滑动窗口算法
- C# 解法二：索引寻找
- Java 解法一：滑动窗口算法
- Java 解法二：遍历字符串
1.题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
- 示例1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 示例 2：
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
- 示例 3：
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
- 提示：
- 每0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
2.题解
C# 解法一：滑动窗口算法
滑动窗口算法（Sliding Window）可以用来解决字符串（数组）的子元素问题，，查找满足一定条件的连续子区间，可以将嵌套的循环问题，转化为单循环问题，降低时间复杂度。
滑动窗口算法需要用到双指针，遍历字符串（数组）时，两个指针都起始于原点，并一前一后地向终点移动，两个指针一前一后夹着的子串（子数组）就像一个窗口，窗口的大小和覆盖范围会随着前后指针的移动而发生变化。
窗口该如何移动需要根据求解的问题来决定，通过左右指针的移动遍历字符串（数组），寻找满足特定条件的连续子区间。
public class Solution {
public int LengthOfLongestSubstring(string s) {
HashSet<char> letter = new HashSet<char>();// 哈希集合，记录每个字符是否出现过
int left = 0,right = 0;//初始化左右指针，指向字符串首位字符
int length = s.Length;
int count = 0,max = 0;//count记录每次指针移动后的子串长度
while(right < length)
{
if(!letter.Contains(s[right]))//右指针字符未重复
{
letter.Add(s[right]);//将该字符添加进集合
right++;//右指针继续右移
count++;
}
else//右指针字符重复，左指针开始右移，直到不含重复字符（即左指针移动到重复字符(左)的右边一位）
{
letter.Remove(s[left]);//去除集合中当前左指针字符
left++;//左指针右移
count--;
}
max = Math.Max(max,count);
}
return max;
}
}
C# 解法二：索引寻找
历所有字符，然后当碰到重复字符时存储值，同时处理List，进行下一队的查找。
public class Solution {
public int LengthOfLongestSubstring(string s) {
List<char> ls = new List<char>();
int n = s.Length;
int intMaxLength = 0;
for (int i = 0; i < n; i++)
{
if (ls.Contains(s[i]))
{
ls.RemoveRange(0, ls.IndexOf(s[i]) + 1);
}
ls.Add(s[i]);
intMaxLength = ls.Count > intMaxLength ? ls.Count : intMaxLength;
}
return intMaxLength;
}
}
Java 解法一：滑动窗口算法
- 我们不妨以示例一中的字符串 abcabcbb\texttt{abcabcbb}abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：
- 以 (a)bcabcbb\texttt{(a)bcabcbb}(a)bcabcbb 开始的最长字符串为 (abc)abcbb\texttt{(abc)abcbb}(abc)abcbb；
- 以 a(b)cabcbb\texttt{a(b)cabcbb}a(b)cabcbb 开始的最长字符串为 a(bca)bcbb\texttt{a(bca)bcbb}a(bca)bcbb；
- 以 ab©abcbb\texttt{ab©abcbb}ab©abcbb 开始的最长字符串为 ab(cab)cbb\texttt{ab(cab)cbb}ab(cab)cbb；
- 以 abc(a)bcbb\texttt{abc(a)bcbb}abc(a)bcbb 开始的最长字符串为 abc(abc)bb\texttt{abc(abc)bb}abc(abc)bb；
- 以 abca(b)cbb\texttt{abca(b)cbb}abca(b)cbb 开始的最长字符串为 abca(bc)bb\texttt{abca(bc)bb}abca(bc)bb；
- 以 abcab©bb\texttt{abcab©bb}abcab©bb 开始的最长字符串为 abcab(cb)b\texttt{abcab(cb)b}abcab(cb)b；
- 以 abcabc(b)b\texttt{abcabc(b)b}abcabc(b)b 开始的最长字符串为 abcabc(b)b\texttt{abcabc(b)b}abcabc(b)b；
- 以 abcabcb(b)\texttt{abcabcb(b)}abcabcb(b) 开始的最长字符串为 abcabcb(b)\texttt{abcabcb(b)}abcabcb(b)。
- 这样一来，我们就可以使用「滑动窗口」来解决这个问题了：
- 我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 rk;
- 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
- 在枚举结束后，我们找到的最长的子串的长度即为答案。
- 判断重复字符
- 在上面的流程中，我们还需要使用一种数据结构来判断 是否有重复的字符，常用的数据结构为哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
Java 解法二：遍历字符串
- 遍历字符串，每次以 i 值记录，不回溯 i 值，用flag记录遍历过程找到的重复的字符的位置。如果遇到重复字符，i-flag 即为子串长度，此时flag重新定位到子串中重复字符的位置，i 继续往后遍历。这里length跟result记录长度
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0;
int flag = 0;
int length = 0;
int result = 0;
while (i < s.length()) {
int pos = s.indexOf(s.charAt(i),flag);
if (pos < i) {
if (length > result) {
result = length;
}
if (result >= s.length() - pos - 1) {
return result;
}
length = i - pos - 1;
flag = pos + 1;
}
length++;
i++;
}
return length;
}
}
