剑指offer-79、最⻓不含重复字符的⼦字符串
<h2 id="题目描述">题目描述</h2><p>请从字符串中找出⼀个最⻓的不包含重复字符的⼦字符串，计算该最⻓⼦字符串的⻓度。</p>
<p>数据范围: ⻓度⼩于40000</p>
<p>示例1<br>
输⼊："abcabcbb"<br>
返回值：3<br>
说明：因为⽆重复字符的最⻓⼦串是"abc"，所以其⻓度为 3。</p>
<p>示例2<br>
输⼊："bbbbb"<br>
返回值：1<br>
说明：因为⽆重复字符的最⻓⼦串是"b"，所以其⻓度为 1</p>
<p>示例3<br>
输⼊："pwwkew"<br>
返回值：3<br>
说明：因为⽆重复字符的最⻓⼦串是 "wke"，所以其⻓度为 3。</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力枚举">暴力枚举</h3>
<p>双层循环枚举所有子串，检查是否包含重复字符</p>
<pre><code class="language-java">public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
int n = s.length();
int maxLen = 0;
// 枚举所有可能的子串起始位置
for (int i = 0; i < n; i++) {
// 枚举所有可能的子串结束位置
for (int j = i; j < n; j++) {
// 检查子串s是否无重复
if (isUnique(s, i, j)) {
maxLen = Math.max(maxLen, j - i + 1);
} else {
break; // 有重复，内层循环可提前结束
}
}
}
return maxLen;
}
// 检查子串s是否无重复字符
private boolean isUnique(String s, int left, int right) {
Set<Character> set = new HashSet<>();
for (int i = left; i <= right; i++) {
char c = s.charAt(i);
if (set.contains(c)) {
return false;
}
set.add(c);
}
return true;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n³)，外层循环n次，内层循环最多n次，isUnique检查O(n)</li>
<li><strong>空间复杂度</strong>：O(min(n,128))，字符集大小有限</li>
</ul>
<h3 id="滑动窗口基础版">滑动窗口（基础版）</h3>
<p>右指针扩展窗口，左指针收缩窗口以消除重复</p>
<p><strong>窗口定义：</strong></p>
<ul>
<li><code>left</code>：窗口左边界</li>
<li><code>right</code>：窗口右边界</li>
<li><code>window</code>：当前窗口内的字符集合</li>
</ul>
<p><strong>执行过程示例（"abcabcbb"）：</strong></p>
<pre><code class="language-text">初始: left=0, right=0, window={}, maxLen=0
1. 添加'a': window={a}, right=1, maxLen=1
2. 添加'b': window={a,b}, right=2, maxLen=2
3. 添加'c': window={a,b,c}, right=3, maxLen=3
4. 添加'a'(重复): 移除s='a', left=1
5. 添加'a': window={b,c,a}, right=4, maxLen=3
...
结果: 3
</code></pre>
<pre><code class="language-java">import java.util.HashSet;
import java.util.Set;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
Set<Character> window = new HashSet<>();
int left = 0, right = 0;
int maxLen = 0;
int n = s.length();
while (right < n) {
char c = s.charAt(right);
// 如果当前字符不在窗口中，扩展窗口
if (!window.contains(c)) {
window.add(c);
right++;
maxLen = Math.max(maxLen, right - left);
}
// 如果当前字符已在窗口中，收缩窗口
else {
window.remove(s.charAt(left));
left++;
}
}
return maxLen;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(2n) = O(n)，每个字符最多被访问两次</li>
<li><strong>空间复杂度</strong>：O(min(n,128))，字符集大小固定</li>
</ul>
<h3 id="优化滑动窗口">优化滑动窗口</h3>
<p>遇到重复字符时，左指针直接跳转到重复字符的下一个位置</p>
<pre><code class="language-java">import java.util.HashMap;
import java.util.Map;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
Map<Character, Integer> charIndex = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符已存在且在当前窗口内
if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
// 左指针直接跳转到重复字符的下一个位置
left = charIndex.get(c) + 1;
}
// 更新字符的最后出现位置
charIndex.put(c, right);
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(min(n,128))</li>
</ul>
<p>进一步优化：使用数组替代HashMap</p>
<p>ASCII字符只有128个，可使用固定数组，即使用int记录字符最后出现的位置，-1表示未出现</p>
<pre><code class="language-java">public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
int[] lastIndex = new int; // ASCII字符集
Arrays.fill(lastIndex, -1); // 初始化为-1表示未出现
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符在当前窗口内出现过
if (lastIndex >= left) {
left = lastIndex + 1; // 直接跳转
}
// 更新字符的最后出现位置
lastIndex = right;
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(1) - 固定128大小</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19648869
頁:
[1]