本文共 2392 字，大约阅读时间需要 7 分钟。

解决方案：找出不含重复字符的最长子串的长度

问题分析

给定一个字符串，找出其中不含有重复字符的最长子串的长度。子串是字符串中连续的一段字符，因此必须是连续的。例如：

• 示例1："abcabcbb" 的最长子串是 "abc"，长度为3。
• 示例2："bbbbb" 的最长子串是 "b"，长度为1。
• 示例3："pwwkew" 的最长子串是 "wke"，长度为3。

解法一：滑动窗口法

思路：使用一个窗口来记录当前的子串，确保窗口内没有重复字符。当遇到重复字符时，调整窗口的起始位置，以确保窗口内字符唯一。记录窗口的最大长度。

步骤：

代码示例：

public class Solution {    public int LengthOfLongestSubstring(string s) {        int[] r = new int[128]; // ASCII码个数        int c = 0, mx = 0;        int i = 0;        for (char item : s) {            if (r[item] >= c) {                c = r[item] + 1;            }            r[item] = i;            int currentLength = i - c + 1;            if (currentLength > mx) {                mx = currentLength;            }            i++;        }        return mx;    }}

时间复杂度：O(n)空间复杂度：O(1)

解法二：固定数组法

思路：使用一个数组记录每个字符的最后出现位置。对于每个字符，计算当前窗口的起始位置，并更新最大长度。

步骤：

代码示例：

public class Solution {    public int LengthOfLongestSubstring(string s) {        int[] r = new int[128];        int c = 0, mx = 0;        int i = 0;        for (char item : s) {            if (r[item] >= c) {                c = r[item] + 1;            }            r[item] = i;            int currentLength = i - c + 1;            if (currentLength > mx) {                mx = currentLength;            }            i++;        }        return mx;    }}

时间复杂度：O(n)空间复杂度：O(1)

解法三：暴力法

思路：遍历所有可能的子串，检查每个子串是否包含重复字符，记录最长的子串长度。

步骤：

代码示例：

public class Solution {    public int LengthOfLongestSubstring(string s) {        int mx = 0;        for (int i = 0; i < s.Length; i++) {            List
   
     r = new ArrayList<>();            for (int j = i + 1; j < s.Length; j++) {                if (r.contains(s.charAt(j))) {                    break;                }                r.add(s.charAt(j));                if (j - i + 1 > mx) {                    mx = j - i + 1;                }            }        }        return mx;    }}
   

时间复杂度：O(n^3)空间复杂度：O(n)

总结

解法一和解法二都是高效的线性时间算法，适合处理长字符串。解法三虽然正确，但效率较低，仅在字符串较短时适用。建议优先选择解法一或解法二。