当前位置：首页 > news >正文

常见算法题目2 - 给定一个字符串，找出其中最长的不重复子串

news 2025/5/24 9:25:01

算法题目2 - 给定一个字符串，找出其中最长的不重复子串

1. 问题描述

给定一个字符串，输出其最长的不重复子串，例如：

String str = "ababc";
输出：
abc

以下根据两种搜索算法。

2. 算法解决

2.1 暴力循环法

通过暴力循环搜索，时间负责度为O(n^3)，效率低，代码如下：

/*** 题目：给定一个字符串，找出其中最长的不重复子串* 暴力法 时间复杂度 O(n^3)* @param str* @return*/private static String longestNoRepStr1(String str) {String result = "";if (str == null || str.length() == 0) {return result;}for (int i = 0; i < str.length(); i++) {for (int j = i; j < str.length(); j++) {// 判断子串是否重复 重复则跳出内层循环if (isRepStr(str, i, j)) {break;}// 不重复则截取比较长度 保留长的String subStr = str.substring(i, j + 1);if (subStr.length() > result.length()) {result = subStr;}}}return result;}

2.2 滑动窗口法

滑动窗口法借助左、右两个指针滚动判断，效率高，时间复杂度为O(n)，代码如下：

 /*** 题目2：给定一个字符串，找出其中最长的不重复子串* 滑动窗口法 时间复杂度  O(n)* @param str* @return*/private static String longestNoRepStr2(String str) {String result = "";if (str == null || str.length() == 0) {return result;}// 左指针int left = 0;// 存储当前最大长度int maxLength = 0;// 存储当前窗口的元素下标Map<Character, Integer> characterMap = new HashMap<>();// 右指针滑动for (int right = 0; right < str.length(); right++) {char c = str.charAt(right);// 如果当前字符重复if (characterMap.containsKey(c)) {// 左指针右移left = Math.max(left, characterMap.get(c) + 1);}// 存储当前字符characterMap.put(c, right);// 当前字符串长度int currentLength = right - left + 1;// 保留长的if (currentLength > maxLength) {maxLength = currentLength;result = str.substring(left, right + 1);}}return result;}

3. 测试

调用测试：

public class LongestNoRepStrTest {public static void main(String[] args) {String str = "ababcd";// 暴力解法String result1 = longestNoRepStr1(str);System.out.println("最长不重复子串，暴力循环法结果：" + result1);System.out.println("====================");// 滑动窗口法String result2 = longestNoRepStr2(str);System.out.println("最长不重复子串，滑动窗口法结果：" + result2);}}