昨天面试一个候选人一个算法题：无重复字符的最长子串

吭哧吭哧半天一行代码没写出来啊，后来我尝试提示他，先从暴力解法入手应该怎么想？还是没思路，哎呀妈想让你面试通过是真的难。

#来点儿干货#​无重复字符的最长子串是一个常见的字符串处理问题，可以通过滑动窗口的方法来解决。滑动窗口是一种数组/字符串问题处理方法，通过维护一个窗口，能够在O(N)的时间复杂度内解决问题。

滑动窗口思路初始化：创建一个整数变量 maxLen 用来保存最长子串的长度，初始化为0。创建两个指针 left 和 right，分别表示窗口的左右边界，初始化都为0。滑动窗口：创建一个哈希集合 HashSet 来存储窗口中的字符，确保字符的唯一性。移动右指针 right 来扩展窗口，每次循环向 HashSet 中添加一个新字符。检查重复：如果新添加的字符在 HashSet 中已存在，说明窗口中有重复字符，此时需要移动左指针 left，并从 HashSet 中移除对应的字符，直到移除了重复的字符。更新最大长度：在每次右指针移动后，更新 maxLen 的值，使其保持为当前最长无重复字符子串的长度。循环结束条件：当右指针 right 移动到字符串的末尾时，结束循环。滑动窗口Java 解法

下面是解决这个问题的 Java 代码实现：

import java.util.HashSet;public class Solution {    public int lengthOfLongestSubstring(String s) {        HashSet<Character> set = new HashSet<>();        int maxLen = 0;        int left = 0;        for (int right = 0; right < s.length(); right++) {            char c = s.charAt(right);            // 如果字符已存在于HashSet中，移动左指针并从HashSet中移除字符            while (set.contains(c)) {                set.remove(s.charAt(left));                left++;            }            // 添加当前字符到HashSet中            set.add(c);            // 更新最大子串长度            maxLen = Math.max(maxLen, right - left + 1);        }        return maxLen;    }    public static void main(String[] args) {        Solution solution = new Solution();        String s = "abcabcbb";        System.out.println(solution.lengthOfLongestSubstring(s)); // 输出应为 3    }}

该代码实现了无重复字符最长子串的查找，并且时间复杂度是O(N)，其中N是字符串的长度。每个字符最多被访问两次（一次是右指针移动，一次是左指针移动）。

上述是效率最高的解法，可能确实不容易想到，但是除此之外还有很多其他解法啊；咱不至于啥也想不到啊。

解法 1：暴力法

这是最直观的方法，枚举所有的子串，然后检查每个子串是否含有重复的字符。这种方法的时间复杂度是O(n^3)，空间复杂度是O(min(n, m))，其中n是字符串的长度，m是字符集的大小。

public class Solution {    public int lengthOfLongestSubstring(String s) {        int n = s.length();        int maxLen = 0;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j <= n; j++) {                if (allUnique(s, i, j)) {                    maxLen = Math.max(maxLen, j - i);                }            }        }        return maxLen;    }    public boolean allUnique(String s, int start, int end) {        Set<Character> set = new HashSet<>();        for (int i = start; i < end; i++) {            Character ch = s.charAt(i);            if (set.contains(ch)) return false;            set.add(ch);        }        return true;    }}

可以对暴力法进行一定的优化，例如，当我们找到一个重复的字符时，不需要从上一个起始位置的下一个字符开始重新检查，而是直接跳过重复的字符。

解法 3：动态规划 + 哈希表

使用动态规划的思想，我们可以记录以第i个字符结尾的最长无重复字符的子串长度，并利用哈希表来存储字符最后一次出现的位置。

import java.util.HashMap;public class Solution {    public int lengthOfLongestSubstring(String s) {        HashMap<Character, Integer> map = new HashMap<>();        int maxLen = 0;        int left = 0;        for (int right = 0; right < s.length(); right++) {            char c = s.charAt(right);            if (map.containsKey(c)) {                left = Math.max(map.get(c) + 1, left);            }            map.put(c, right);            maxLen = Math.max(maxLen, right - left + 1);        }        return maxLen;    }}

在这个解法中，我们利用哈希表来降低时间复杂度，使得每个字符只需要被访问一次，从而将时间复杂度降低到O(n)。

解法 4：使用数组作为简易哈希表

如果字符集较小，比如只有ASCII字符，我们可以使用一个整数数组代替哈希表来存储字符的索引，从而进一步提高效率。

public class Solution {    public int lengthOfLongestSubstring(String s) {        int[] index = new int[128]; // 假设字符集为ASCII        int maxLen = 0;        for (int right = 0, left = 0; right < s.length(); right++) {            char c = s.charAt(right);            left = Math.max(index[c], left);            maxLen = Math.max(maxLen, right - left + 1);            index[c] = right + 1; // 更新字符的索引位置        }        return maxLen;    }}

在这个解法中，数组 index 用来存储每个字符最后一次出现的位置的下一个位置，这样可以直接跳过重复的字符。

所有这些方法中，滑动窗口和动态规划+哈希表是最常用且效率最高的，尤其是在处理大型数据或者字符集较大的情况下。