算法题3 — 求字符串中的最长子串

题目

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

示例

示例1

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例2

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例3

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

解题

解法1

粗暴破解，找一个最长子串，那么我们用两个循环穷举所有子串，然后再用一个函数判断该子串中有没有重复的字符。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;/*** @author zxn* @ClassName LongestSubstring* @Description* @createTime 2023年05月24日 20:33:00*/
public class LongestSubstring {public static void main(String[] args) {String s = "abcabcbb";int i = lengthOfLongestSubstring1(s);System.out.println("i="+i);}private static int lengthOfLongestSubstring1(String s) {int n = s.length();int len=0;for (int i = 0; i < n; i++) {for (int j = i+1; j < n; j++) {if (unique(s,i,j)){len = Math.max(len,j-i+1);}}}return len;}public static boolean unique(String s, int start, int end) {Set<Character> set = new HashSet<>();for (int i = start; i <= end; i++) {if (set.contains(s.charAt(i))){return false;}set.add(s.charAt(i));}return true;}

解法2

上边的算法中，我们假设当 i 取 0 的时候，

j 取 1，判断字符串 str[0,1) 中有没有重复的字符。

j 取 2，判断字符串 str[0,2) 中有没有重复的字符。

j 取 3，判断字符串 str[0,3) 中有没有重复的字符。

j 取 4，判断字符串 str[0,4) 中有没有重复的字符。

做了很多重复的工作，因为如果 str[0,3) 中没有重复的字符，我们不需要再判断整个字符串 str[0,4) 中有没有重复的字符，而只需要判断 str[3] 在不在 str[0,3) 中，不在的话，就表明 str[0,4) 中没有重复的字符。

如果在的话，那么 str[0,5) ，str[0,6) ，str[0,7) 一定有重复的字符，所以此时后边的 j 也不需要继续增加了。i ++ 进入下次的循环就可以了。

此外，我们的 j 也不需要取 j + 1，而只需要从当前的 j 开始就可以了。

判断一个字符在不在字符串中，我们需要可以遍历整个字符串，遍历需要的时间复杂度就是 O（n），加上最外层的 i 的循环，总体复杂度就是 O（n²）。我们可以继续优化，判断字符在不在一个字符串，我们可以将已有的字符串存到 Hash 里，这样的时间复杂度是 O（1），总的时间复杂度就变成了 O（n）。

当 j 指向的 字符 存在于前边的子串中，此时 i 向前移到 b ,此时子串中仍然含有字符，还得继续移动，所以这里其实可以优化。我们可以一步到位，直接移动到子串的位置的下一位！

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;/*** @author zxn* @ClassName LongestSubstring* @Description* @createTime 2023年05月24日 20:33:00*/
public class LongestSubstring {public static void main(String[] args) {String s = "abcabcbb";int i = lengthOfLongestSubstring2(s);System.out.println("i="+i);}private static int lengthOfLongestSubstring2(String s) {int n = s.length();int len = 0;Map<Character, Integer> map = new HashMap<>();for (int i = 0, j = 0; j < n; j++) {if (map.containsKey(s.charAt(j))) {i = Math.max(i, map.get(s.charAt(j)));}map.put(s.charAt(j), j + 1);len = Math.max(len, j - i + 1);}return len;}
}

leetcode

leetcode地址