没有重复字符的最长子串

没有重复字符的最长子串的算法分析

要找到没有重复字符的最长子串，可以采用滑动窗口（Sliding Window）技术，这是一种高效的线性时间复杂度算法。以下是详细的分析和实现：

算法思路

滑动窗口：使用两个指针（left和right）表示当前窗口的左右边界。窗口内的子串始终保持无重复字符。
哈希表：使用一个数组（大小为256，覆盖所有ASCII字符）来记录每个字符最后一次出现的位置。
窗口调整：
当右指针（right）指向的字符已经在当前窗口中出现过（即哈希表中记录的位置不小于left），则将左指针（left）移动到该字符上次出现位置的下一个位置。
更新哈希表中当前字符的位置为右指针的位置。
每次移动右指针后，计算当前窗口的长度（right - left + 1），并更新最大长度。

代码实现import java.util.Arrays;class Solution { public int lengthOfLongestSubstring(String s) { int[] hash = new int[256]; // 用于记录字符最后一次出现的位置 Arrays.fill(hash, -1); // 初始化为-1，表示字符未出现过 int left = 0, right = 0; int max = 0; while (right < s.length()) { char c = s.charAt(right); if (hash[c] != -1) { // 字符c已经出现过 if (hash[c] >= left) { // 如果上次出现的位置在当前窗口内 left = hash[c] + 1; // 移动左指针到重复字符的下一个位置 } } max = Math.max(max, right - left + 1); // 更新最大长度 hash[c] = right; // 更新字符c的最后出现位置 right++; // 移动右指针 } return max; }}复杂度分析

时间复杂度（TC）：O(n)，其中n是字符串的长度。每个字符最多被访问两次（一次由右指针，一次由左指针）。
空间复杂度（SC）：O(256)，即O(1)。使用固定大小的数组来存储字符的最后出现位置。

示例说明

以字符串 "abcabcbb" 为例：

初始化：left = 0, right = 0, max = 0, hash数组全为-1。
right = 0, c = 'a'：
hash['a'] = -1，未出现过。
max = max(0, 0-0+1) = 1。
hash['a'] = 0。
right++。
right = 1, c = 'b'：
hash['b'] = -1，未出现过。
max = max(1, 1-0+1) = 2。
hash['b'] = 1。
right++。
right = 2, c = 'c'：
hash['c'] = -1，未出现过。
max = max(2, 2-0+1) = 3。
hash['c'] = 2。
right++。
right = 3, c = 'a'：
hash['a'] = 0，已出现过且0 >= left（0）。
left = hash['a'] + 1 = 1。
max = max(3, 3-1+1) = 3。
hash['a'] = 3。
right++。
继续处理直到right = 8，最终max = 3（子串 "abc" 或 "bca" 等）。

总结

滑动窗口技术通过动态调整窗口的左右边界，确保窗口内始终是无重复字符的子串。哈希表（或数组）用于快速判断字符是否重复及其位置。该算法高效且易于实现，适用于解决类似的无重复字符子串问题。

您可能感兴趣问答

Collapsible

热门标签

热点问答