Java日常练习题,每天进步一点点(52)

Java日常练习题,每天进步一点点(52) -- 完整攻略

问题描述

这道练习题的问题描述如下：

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

思路分析

为了解决这个问题，我们需要思考以下几个方面：

1. 如何判断一个字符串是否包含重复字符？
2. 如何确定最长子串？
3. 如何实现算法？

这里我们给出一种基于滑动窗口的解法：

1. 定义两个指针l, r，并初始化为0，表示左右窗口边界。
2. 然后定义一个set集合，用于存储s中子串的字符。
3. 设定一个变量max_length，存储最长子串的长度，初值为0。
4. 当 r < s.length时，每次将 s[r] 加入 set 中：
5. 如果 s[r] 不在 set 中，表示当前子串不包含重复字符，则更新max_length为 set 的大小，并将 r++。
6. 如果 s[r] 已经在 set 中，我们就需要找到一个位置 l'，使得s[l'] == s[r]，并将[l, l']中的元素从 set 删除，然后更新 max_length，r++，l = l' + 1。
7. 重复执行上述操作，直到 r = s.length。

示例代码

public static int lengthOfLongestSubstring(String s) {
    int max_length = 0;
    Set<Character> set = new HashSet<>();
    int l = 0, r = 0;

    while (r < s.length()) {
        if (!set.contains(s.charAt(r))) {
            set.add(s.charAt(r));
            max_length = Math.max(max_length, set.size());
            r++;
        } else {
            set.remove(s.charAt(l));
            l++;
        }
    }

    return max_length;
}

示例输出

例如，对于输入字符串 s = "abcabcbb"，执行 lengthOfLongestSubstring(s) 的结果为 3。输出过程如下：

System.out.println(lengthOfLongestSubstring("abcabcbb"));

输出结果为：

3