原题
请从字符串中找出一个最长的不蕴含反复字符的子字符串，计算该最长子字符串的长度。
思路1
- 双指针+HashSet
- 当不是反复的字符，放进set并且i++；res记录最大长度
- 当遇到j指向的字符放不进去，就删掉后面的字符并且i++，直到指向的字符能放进去
- 工夫复杂度 O（2n）
代码1
package offer;import java.util.HashSet;import java.util.Scanner;import java.util.Set;/** * 请从字符串中找出一个最长的不蕴含反复字符的子字符串，计算该最长子字符串的长度。 */public class offer48 { public static void main(String[] args) { Scanner scc=new Scanner(System.in); String s=scc.next(); System.out.println(new Solution48().lengthOfLongestSubstring(s)); }}class Solution48 { public int lengthOfLongestSubstring(String s) { int n=s.length(); Set<Character> set =new HashSet<>(); int res =0,i=0,j=0; while(i<n&&j<n) { if(!set.contains(s.charAt(j))) {//当不是反复的字符，放进set并且i++；res记录最大长度 set.add(s.charAt(j++)); res=Math.max(res, j-i); } else { set.remove(s.charAt(i++));//当遇到j指向的字符放不进去，就删掉后面的字符并且i++，直到指向的字符能放进去 } } return res; }}思路2
- 应用动静布局和hashmap
- 思路1在要害上是迭代寻找反复字符首次呈现，能够应用hashmap来找，<String,Integer>,发现反复时就更新value，省去了i的从前往后遍历
代码2
看官网题解