算法题目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);}}
打印结果：
可见，输出结果一致
