Skip to content

无重复字符的最长子串

无重复字符的最长子串（Longest Substring Without Repeating Characters）要求找出给定字符串中最长的没有重复字符的子串。下面是用Java实现的解决方案：

import java.util.HashMap;

public class LongestSubstringWithoutRepeatingCharacters {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0; // 记录最长无重复字符子串的长度
        int start = 0; // 记录当前无重复字符子串的起始位置
        HashMap<Character, Integer> map = new HashMap<>(); // 存储字符及其最近出现的位置

        // 遍历字符串
        for (int end = 0; end < s.length(); end++) {
            char currentChar = s.charAt(end);
            // 如果当前字符已经在子串中出现过，则更新起始位置为当前字符最近出现位置的下一个位置
            if (map.containsKey(currentChar)) {
                start = Math.max(start, map.get(currentChar) + 1);
            }
            // 更新当前字符最近出现的位置
            map.put(currentChar, end);
            // 更新最长无重复字符子串的长度
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }
}

解释每一步：

  1. 我们使用两个指针 start 和 end 来定义当前无重复字符子串的起始位置和结束位置。

  2. 使用HashMap来存储字符及其最近出现的位置。

  3. 我们遍历字符串，对于每个字符：

  4. 如果当前字符已经在子串中出现过，则更新起始位置为当前字符最近出现位置的下一个位置。
  5. 更新当前字符最近出现的位置。

  6. 更新最长无重复字符子串的长度。

  7. 返回最长无重复字符子串的长度。

这种解法的时间复杂度为 O(n)，其中 n 是字符串的长度。因为我们只需要遍历一次字符串。空间复杂度为 O(min(m, n))，其中 m 是字符集的大小，n 是字符串的长度。因为HashMap最多存储字符集大小的键值对。