算法：无重复字符的最长子串

「这是我参与11月更文挑战的第11天，活动详情查看：2021最后一次更文挑战」

前言

今天这道题是比较常见的一种类型，在面试中也时不时会遇到，难度也是不低的，力扣通过率也只有38.2%而已，我们一起来看下吧。

题目描述

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

• 示例 1:

输入: s = "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

• 示例 2:

输入: s = "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

• 示例3

输入: s = "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

• 示例4

输入: s = ""

输出: 0

• 提示：

0. 0 <= s.length <= 5 * 104
1. s 由英文字母、数字、符号和空格组成

题目分析

本题采用暴力解法时间复杂度较高，会达到 O(n^2)，自然是不推荐的。

本题可以定义一个 map 集合，其中 key 值为字符，value 值为字符位置 +1，之所以加 1 是为了从字符位置后一个才开始不重复 定义开始位置为 left，然后开始遍历，在遍历过程中，会遇到与 [left, right] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 left，此时 [left, right] 区间内不存在重复字符。 无论是否更新 left，都会更新map和结果 res。

时间复杂度：时间复杂度：O(n)

代码示例

class Solution {
    /**
     * map (k, v)，其中 key 值为字符，value 值为字符位置;
     */
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), res = 0, left =0;
        Map<Character, Integer> map = new HashMap<>();
        for (int right = 0; right < n; right++) {
            char alpha = s.charAt(right);
            if (map.containsKey(alpha)) {
                left = Math.max(map.get(alpha), left);
            }
            res = Math.max(res, right - left + 1);
            map.put(s.charAt(right), right + 1);
        }
        return res;
    }
}
复制代码

此外，还可以参考官网给出的另一种写法：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}
复制代码