原题
请从字符串中找出一个最长的不蕴含反复字符的子字符串,计算该最长子字符串的长度。
思路 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
看官网题解