【算法】滑动窗口动态查找不含重复字符的最长子串

//        给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
//
//        输入: s = "abcabcbb"
//        输出: 3String s = "abcabcbb";String[] sArr = s.split("");StringBuilder noDuplicateStr = new StringBuilder();for (int i = 0; i < sArr.length; i++) {for (int j = i + 1; j < sArr.length; j++) {if (sArr[i].equals(sArr[j])) {continue;}if (noDuplicateStr.toString().contains(sArr[j])) {continue;}noDuplicateStr.append(sArr[i]).append(sArr[j]);}}System.out.println(noDuplicateStr.toString().length());

以上实现逻辑存在题，无法正确找到 不含有重复字符的最长子串 的长度。你能指出存在哪些问题吗？

---

❌ 当前代码存在的问题：

1. noDuplicateStr 是通过拼接字符的方式构造的，但这种方式不能保证字符顺序和连续性。
2. 双重循环的逻辑错误，导致重复字符无法正确判断。
3. 使用 StringBuilder.contains() 方法并不能准确追踪无重复字符的子串。
4. 最终输出的 length() 并不是“最长无重复子串”的长度，而是 noDuplicateStr 的长度，这与题目要求不符。

---

✅ 正确解法（滑动窗口算法）：

这是一个经典的 滑动窗口（Sliding Window） 问题，可以通过维护一个窗口来动态查找不含重复字符的最长子串。

public class Solution {public static int lengthOfLongestSubstring(String s) {int n = s.length();int maxLength = 0;int left = 0;HashMap<Character, Integer> charIndexMap = new HashMap<>();for (int right = 0; right < n; right++) {char currentChar = s.charAt(right);// 如果字符已出现且在窗口内，则移动左指针到该字符上次出现位置的右边if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= left) {left = charIndexMap.get(currentChar) + 1;}// 更新当前字符的位置charIndexMap.put(currentChar, right);// 计算当前窗口长度并更新最大值maxLength = Math.max(maxLength, right - left + 1);}return maxLength;}public static void main(String[] args) {String s = "abcabcbb";System.out.println(lengthOfLongestSubstring(s)); // 输出: 3}
}

---

🔍 示例说明：

对于输入 s = "abcabcbb"，最长无重复字符的子串是 "abc"，其长度为 3。

---

🧠 算法复杂度分析：

• 时间复杂度：O(n)，其中 n 是字符串长度，每个字符最多被访问一次。
• 空间复杂度：O(min(m, n))，m 是字符集大小（如 ASCII 字符集为 128）。

---

💡 建议：

• 使用 HashMap 来记录字符最后一次出现的位置。
• 使用双指针（left 和 right）来维护当前窗口。
• 这种方式效率高，适用于大多数类似子串问题。