程序设计－无重复字符的最长子串（Java）

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程​https://www.captainai.net/troubleshooterpackage live.every.day.bytedance; import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.assertEquals; /** * 无重复字符的最长子串 * * 题目描述 * 给定一个字符串s请你计算出其中不含有重复字符的最长子串的长度。 * 提示 * 0 s.length 5 * 1024 * s由英文字母、数字、符号和空格组成。 * * 示例1 * 输入s abcabcbb * 输出3 * 解释因为无重复字符的最长子串是abc所以其长度为3。 * * 示例2 * 输入s bbbbb * 输出1 * 解释因为无重复字符的最长子串是b所以其长度为1。 * * 示例3 * 输入s pwwkew * 输出3 * 解释因为无重复字符的最长子串是wke所以其长度为3。请注意你的答案必须是子串的长度pwke是一个子序列不是 * 子串。 * * author LiveEveryDay */ public class NoDupCharMaxSubstringTest { Test public void testNoDupCharMaxSubstring01() { String s abcabcbb; int res NoDupCharMaxSubstring.length(s); assertEquals(3, res); } Test public void testNoDupCharMaxSubstring02() { String s bbbbb; int res NoDupCharMaxSubstring.length(s); assertEquals(1, res); } Test public void testNoDupCharMaxSubstring03() { String s pwwkew; int res NoDupCharMaxSubstring.length(s); assertEquals(3, res); } }package live.every.day.bytedance; import java.util.HashSet; import java.util.Set; /** * 无重复字符的最长子串 * * 题目描述 * 给定一个字符串s请你计算出其中不含有重复字符的最长子串的长度。 * 提示 * 0 s.length 5 * 1024 * s由英文字母、数字、符号和空格组成。 * * 示例1 * 输入s abcabcbb * 输出3 * 解释因为无重复字符的最长子串是abc所以其长度为3。 * * 示例2 * 输入s bbbbb * 输出1 * 解释因为无重复字符的最长子串是b所以其长度为1。 * * 示例3 * 输入s pwwkew * 输出3 * 解释因为无重复字符的最长子串是wke所以其长度为3。请注意你的答案必须是子串的长度pwke是一个子序列不是 * 子串。 * * ---------------- * * 这是一道经典的滑动窗口问题。我们可以使用滑动窗口来解决这个问题。 * * 解题思路 * 1. 定义窗口使用一个集合 Set 来维护当前窗口内的字符保证窗口内没有重复字符。 * 2. 移动窗口 * 使用两个指针 left 和 right初始时都指向字符串的开头。 * right 指针向右移动尝试扩展窗口。 * 如果 s.charAt(right) 已经在集合中说明出现了重复字符则移动 left 指针向右并从集合中移除对应的字符直 * 到窗口内不再包含重复的 s.charAt(right)。 * 如果 s.charAt(right) 不在集合中将其加入集合并更新最大长度。 * 3. 记录结果每次窗口扩展成功时计算当前窗口的长度 right - left 1并与历史最大长度比较取较大值。 * * author LiveEveryDay */ public class NoDupCharMaxSubstring { public static int length(String s) { if (s null || s.isEmpty()) { return 0; } // 使用哈希集合记录窗口内的字符 SetCharacter set new HashSet(); int maxLength 0; int left 0; for (int right 0; right s.length(); right) { char c s.charAt(right); // 如果窗口内已经存在该字符则将窗口左边界右移直到窗口内不再存在该字符 while (set.contains(c)) { set.remove(s.charAt(left)); } // 将当前字符添加到窗口内 set.add(c); // 更新最大长度 maxLength Math.max(maxLength, right - left 1); } return maxLength; } }