面试官：如何找出字符串中无重复最长子串？

要找出字符串中无重复字符的最长子串，推荐使用滑动窗口算法，其时间复杂度为O(n)，能高效解决问题。以下是具体步骤和实现思路：

滑动窗口算法原理

滑动窗口通过维护一个动态变化的窗口（子串范围），利用双指针（左指针left和右指针right）逐步扩展和收缩窗口，确保窗口内无重复字符，并记录满足条件的最长窗口长度。

具体步骤

初始化指针和集合：
left = 0，表示窗口左边界；
max_length = 0，记录最长子串长度；
使用哈希集合（如HashSet）存储窗口内字符，实现快速判重。
扩展右边界：
遍历字符串，右指针right从0开始向右移动。
若当前字符s[right]不在集合中，将其加入集合，并更新max_length为当前窗口大小（right - left + 1）与历史最大值的较大者。
若字符已存在，说明窗口内出现重复，需收缩左边界。
收缩左边界：
从集合中移除s[left]，并将left右移一位，直到窗口内不再包含重复字符。
重复扩展右边界的步骤，继续寻找更长的无重复子串。
终止条件：
当right遍历完整个字符串时，算法结束，返回max_length。

示例演示

以字符串"abcabcbb"为例：

初始窗口[0,0]（空），max_length = 0。
扩展右边界至right=2，窗口为"abc"，无重复，max_length = 3。
遇到重复字符'a'（right=3），移动left至1，窗口变为"bca"。
继续扩展至right=5，窗口为"cab"，更新max_length仍为3。
最终遍历结束，返回max_length = 3。

图：滑动窗口在数组中的移动过程（类似逻辑可应用于字符串）代码实现（Java）import java.util.HashSet;import java.util.Set;class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int max_length = 0; Set<Character> set = new HashSet<>(); int left = 0; for (int right = 0; right < n; right++) { char currentChar = s.charAt(right); // 若字符重复，移动左指针并移除对应字符 while (set.contains(currentChar)) { set.remove(s.charAt(left)); left++; } set.add(currentChar); max_length = Math.max(max_length, right - left + 1); } return max_length; }}关键点说明

哈希集合的作用：快速判断字符是否重复，确保窗口内无重复字符。
双指针的移动：右指针负责扩展窗口，左指针在遇到重复时收缩窗口，保证算法效率。
时间复杂度：O(n)，每个字符最多被访问两次（一次由右指针，一次由左指针）。
空间复杂度：O(min(m, n))，其中m是字符集大小（如ASCII字符集为128），n是字符串长度。

优化方向

若字符集有限（如仅小写字母），可用数组替代哈希集合，进一步优化常数时间。
记录字符最后出现位置，可跳过部分重复字符的移动，但需额外空间存储位置信息。

通过滑动窗口算法，可高效解决无重复字符最长子串问题，适用于面试和实际开发场景。

您可能感兴趣问答

Collapsible

热门标签

热点问答