LeetCode 3：无重复字符的最长子串问题及代码报错排查

给定一个字符串s，找出其中不含重复字符的最长子串（substring）的长度。

示例 #

• 示例1：
  输入：s = "abcabcbb"
  输出：3
  解释：答案是"abc"，长度为3。
• 示例2：
  输入：s = "bbbbb"
  输出：1
  解释：答案是"b"，长度为1。
• 示例3：
  输入：s = "pwwkew"
  输出：3
  解释：答案是"wke"，长度为3。注意答案必须是substring，"pwke"是subsequence而非substring。

约束条件 #

• 0 <= s.length <= 5 * 10^4
• s由英文字母、数字、符号和空格组成。

提交代码 #

class Solution 
{
    public boolean validate(String ret, String s, char temp)
    {
            for(int j = 0; j < ret.length(); j++)
            {
                if(ret.charAt(j) == temp)
                {
                    return true;
                }

            }

        return false;
    }

    public int lengthOfLongestSubstring(String s) 
    {
        String  ret = new String();
        boolean flag = false;
        char temp;
        int highest = 0;

        for(int i = 0; i < s.length(); i++)
        {
            for(int j = 1; j <  s.length(); j++) 
            {
                ret = s.substring(i,j);

                if(ret.length() > 1 && ret.length() < s.length()-1)
                {
                    if(validate(ret, s, s.charAt(j+1)))
                        if(ret.length() > highest)
                            highest = ret.length();
                }
                    
            }      
        } 

        return highest;
    }
}

运行时错误 #

java.lang.StringIndexOutOfBoundsException: 索引8超出长度8的范围
  at line 55, java.base/jdk.internal.util.Preconditions$1.apply
  at line 52, java.base/jdk.internal.util.Preconditions$1.apply
  at line 213, java.base/jdk.internal.util.Preconditions$4.apply
  at line 210, java.base/jdk.internal.util.Preconditions$4.apply
  at line 98, java.base/jdk.internal.util.Preconditions.outOfBounds
  at line 106, java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex
  at line 302, java.base/jdk.internal.util.Preconditions.checkIndex
  at line 4828, java.base/java.lang.String.checkIndex 
  at line 46, java.base/java.lang.StringLatin1.charAt
  at line 1555, java.base/java.lang.String.charAt
  at line 32, Solution.lengthOfLongestSubstring
  at line 54, __DriverSolution__.__helper__
  at line 84, __Driver__.main

错误原因 #

运行时错误是StringIndexOutOfBoundsException，根源在代码里的s.charAt(j+1)：

• 内层循环j的上限是s.length()-1，当j取到s.length()-1时，j+1就等于s.length()，而字符串的索引范围是0到length()-1，此时访问必然越界。
• 除此之外，原代码逻辑还存在多处问题：比如仅判断长度大于1且小于s.length()-1的子串，会漏掉长度为1或等于s.length()的合法情况；双重循环暴力枚举的效率极低，面对长度5e4的字符串会超时；validate方法的逻辑没有正确追踪最长无重复子串的完整过程。

修正后的代码 #

推荐使用滑动窗口（双指针）+哈希表的解法，时间复杂度O(n)，空间复杂度O(min(m,n))（m为字符集大小）：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希表存储字符到其最新索引的映射
        java.util.HashMap<Character, Integer> charMap = new java.util.HashMap<>();
        int maxLength = 0;
        int left = 0; // 滑动窗口左边界

        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            // 如果当前字符已在窗口内，将左边界移至重复字符的下一位（取较大值避免左边界回退）
            if (charMap.containsKey(currentChar) && charMap.get(currentChar) >= left) {
                left = charMap.get(currentChar) + 1;
            }
            // 更新当前字符的最新索引
            charMap.put(currentChar, right);
            // 计算当前窗口长度，更新最大值
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

代码说明 #

1. 滑动窗口：用left和right两个指针表示当前无重复子串的左右边界，right指针持续向右扩展窗口范围。
2. 哈希表：记录每个字符最后一次出现的索引，遇到重复字符时，直接将left指针移动到重复字符的下一个位置，确保窗口内始终无重复字符。
3. 边界处理：覆盖了空字符串、全重复字符、无重复字符等所有场景，彻底避免了索引越界问题。

内容的提问来源于stack exchange，提问作者Mitch