剑指offer第48题无重复字符的最长子串（尺取法和动态规划）

问题描述&＃xff1a;

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

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"&＃xff0c;所以其长度为 3。


示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"&＃xff0c;所以其长度为 1。


示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"&＃xff0c;所以其长度为 3。


请注意&＃xff0c;你的答案必须是 子串 的长度&＃xff0c;"pwke" 是一个子序列&＃xff0c;不是子串。


题目链接&＃xff1a;https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

解题思路&＃xff1a;

  这题使用暴力法双层循环遍历所有子串会超时&＃xff0c;为了避免超时&＃xff0c;使用尺取法。尺取法非常适合用于查找字符串中符合特定要求的子串。**尺取法通常是指保留数组的一对下标&＃xff08;起点和终点&＃xff09;&＃xff0c;然后根据实际情况交替推进两个端点直到得出答案。**这种操作很像尺取虫的爬行方式&＃xff0c;故而得名。

类似的题目有&＃xff1a;

• 最短生成摘要
• hiho字符串

代码实现&＃xff1a;

import java.util.HashSet;public class text03无重复字符的最长子串 {public static void main(String[] args) {String str &＃61; "dvdf";System.out.println(lengthOfLongestSubstring(str));}public static int lengthOfLongestSubstring(String s) {int res &＃61; 0;char[] arr &＃61; s.toCharArray();int star &＃61; 0;int end &＃61; 0;while(star<&＃61;end && end<arr.length){HashSet<Character> set &＃61; new HashSet<Character>();for(int i&＃61;star; i<&＃61;end; i&＃43;&＃43;){set.add(arr[i]);}if(set.size()&＃61;&＃61;(end-star&＃43;1)){ //无重复if(set.size()>res){res &＃61; set.size();}end&＃43;&＃43;;}else{ //有重复star&＃43;&＃43;;}}return res;}
}

提交结果&＃xff1a;

  上面的解法可以优化&＃xff0c;右指针的遍历不变&＃xff0c;左指针的遍历可以进行优化。我们可以在右指针遍历的时候记录字符出现的最后位置。假设右指针当前在的位置是j&＃xff0c;当左指针移动时我们可以直接将左指针移动到上一次字符s[j]最后出现的位置i&＃xff08;注意要与左指针原来的位置进行比较&＃xff0c;因为字符最后出现的位置不一定更靠后&＃xff09;&＃xff1b;因为再左指针移动到i位置之前都是会出现重复的&＃xff0c;所以可以直接移动到i位置。这样可以加快了左指针的移动速度&＃xff0c;减少了重复子串的判断。

代码如下&＃xff1a;

public int lengthOfLongestSubstring(String s) {int res &＃61; 0;char[] arr &＃61; s.toCharArray();Map<Character,Integer> dic &＃61; new HashMap<Character, Integer>(); //记录字符最后出现的位置。//j表示右指针&＃xff0c;i表示左指针int i &＃61; -1;for(int j&＃61;0; j<arr.length; j&＃43;&＃43;) {if(dic.containsKey(arr[j])) {i &＃61; Math.max(dic.get(arr[j]), i); //更细左指针,注意要比较&＃xff0c;因为字符最后出现的位置不一定更靠后}dic.put(arr[j], j); //记录字符出现的组后位置res &＃61; Math.max(res, j-i); }return res;}


提交结果&＃xff1a;

这个优化的方法本质上和动态规划右类似的地方。

参考文章&＃xff1a;
双指针和动态规划