LeetCode题解 -- 3. 无重复字符的最长子串

来自 gpt 的摘要： 本文介绍了如何解决 LeetCode 上的一道题目，即找出字符串中不含重复字符的最长子串的长度。该问题可以使用滑动窗口技术来解决，利用 HashMap 记录字符及其下标，通过动态调整左右指针来维护不重复子串的长度，从而在一次遍历中得出结果。时间复杂度为 O(N)，空间复杂度为 O(1)。代码实现中，左指针和右指针分别表示当前窗口的左右边界，通过不断更新左指针的位置来确保窗口内没有重复字符，并动态计算最长子串的长度。文中详细解释了滑动窗口的核心思路和关键代码实现细节，并提供了 Java 代码示例。更多解法将在后续更新中介绍，如果有任何疑问或发现题解中的问题，欢迎在评论区提出。

题目

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

题目链接

解题思路

1）解题宏观思路

通过题目意思，我们大致可以推断出这是一道滑动窗口的题目，需要我们记录左指针和右指针来求出答案。

2）题目关键词提取

• 不含有重复字符：可以采用 Set 或 Map 进行去重，根据题目意思，我们需要通过记录字母下标来算出字串长度，因此我们选用 HashMap，其中 K 为 Character（字母），V 为 Integer（字母对应的下标）。
• 子串：意味着我们需要采用滑动窗口的思路来解题。

3）复杂度估计

• 我们采用滑动窗口的思路可以一次遍历就求出所有情况，并从中得到答案，因此时间复杂度为 O(N)。
• HashMap 只需要记录 ASCII 码 0 ~ 127 的字符范围，因此空间复杂度为 O(1)。
• 综上，根据题目给出的数据规模，该思路可以实现。

代码实现

1）变量：

• l 表示动态左指针，从 -1 下标开始，无需关注越界问题。
• r 表示动态右指针，从 0 下标开始，需要小于 s.length() 防止越界。
• ans 表示答案，在遍历中动态改变并最终输出。

2）参考代码：

class Solution
{
    public static Map<Character, Integer> map;

    public int lengthOfLongestSubstring(String s)
    {
        map = new HashMap<>();
        int n = s.length();
        // 要点 1 ：l 和 r 左开右闭
        int l = -1;
        int r = 0;
        int ans = 0;

        for (; r < n; r++)
        {
            char c = s.charAt(r);
            if (map.containsKey(c))
            {
                // 要点 2 ：需要取最大值保证 l 不会回退
                l = Math.max(l, map.get(c));
            }
            map.put(c, r);
            ans = Math.max(ans, r - l);
        }

        return ans;
    }
}

3）要点解析：

• 要点 1： 为什么 l 和 r 采用左开右闭进行记录？
  • 左开右闭只需要两者相减就能求出对应长度。
  • 左开右闭的含义是右指针纳入窗口范围，而左指针不纳入窗口范围，当右指针与窗口内重复时，左指针就可以直接赋值 map 对应的下标，保证窗口内恰好处于一个不重复子串的情况。
• 要点 2： 为什么 l 需要取最大值，而不是直接把 map 的值赋给 l ？
  • 举个例子，当 s 的情况是 ab₁c₁c₂b₂a（脚标用来区分不同位置的 b 和 c），且 l 指向 c₁，r 指向 b₂ 时，假如不进行最大值的判断，l 的下标就会被赋为 b₁ 的位置，这时窗口的情况就从 c₂b₂ 变成了 c₁c₂b₂，这显然是不应该发生的。由此可见，我们必须保证 l 的值是递增的。

总结

这里先简单介绍一下哈希表 + 滑动窗口的做法，后续将更新其他的做法，如果有什么疑惑或题解有什么问题，欢迎在评论区指出！