1.蛮力方法
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null){
throw new NullPointerException();
}
if(s.isEmpty()){
return 0;
}
if(s.length()==1){
return 1;
}
String sbTemp;
String sbMax = s.substring(0,1);
int length = s.length();
for (int i =0;i<length;i++){
for (int j = i+1;j<length;j++){
sbTemp = s.substring(i,j);
boolean b = sbTemp.contains(String.valueOf(s.charAt(j)));
if(b)
break;
else
sbTemp = s.substring(i,j+1);
sbMax = (sbTemp.length() > sbMax.length()) ? sbTemp : sbMax;
}
}
return sbMax.length();
}
}
2.改进，用上hashmap中的containsKey方法
此种方法，在判断字符串是否包含对应的字符时，用到了hashmap中的containsKey方法，上述方法中String类中的contains方法，实际调用的是indexOf方法，底层还是去遍历了字符数组；而hashmap中的containsKey方法，在HashMap中，key被存储到hash表中，查找时是在hash表上进行查找，其时间复杂度为：最好情况便是O(1)，最坏情况是O(lgn)
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null){
throw new NullPointerException();
}
if(s.isEmpty()){
return 0;
}
if(s.length()==1){
return 1;
}
String sbTemp;
String sbMax = s.substring(0,1);
int length = s.length();
for (int i =0;i<length;i++){
HashMap<Character, Integer> hashMap = new HashMap<>();
for (int j = i;j<length;j++){
sbTemp = s.substring(i,j+1);
if(hashMap.containsKey(s.charAt(j)))
break;
sbMax = (sbTemp.length() > sbMax.length()) ? sbTemp : sbMax;
hashMap.put(s.charAt(j),j);
}
}
return sbMax.length();
}
}
3.再次改进，滑动窗口
3.再次改进，滑动窗口 算法简介
滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。
可以想象成队列，一端在push元素，另一端在pop元素，如下所示：
假设有数组[a b c d e f g h]
一个大小为3的滑动窗口在其上滑动，则有:
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
适用范围
1、一般是字符串或者列表
2、一般是要求最值（最大长度，最短长度等等）或者子序列
ps：这个滑动窗口的大小可以更具情况来调节大小，即滑动窗口的大小可以动态变化。
算法思想
1、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。
2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。
3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达序列的尽头。
思路其实很简单：第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null)
throw new NullPointerException();
if(s.isEmpty())
return 0;
if(s.length()==1)
return 1;
//左右边界,找到最大的后，整体向右移动
int max = 0;
int leftIndex = 0,rightIndex = 0;
HashMap<Character, Integer> hashMap = new HashMap<>();
hashMap.put(s.charAt(0),0);
for (int i = 1;i<s.length();i++){
if(hashMap.containsKey(s.charAt(i))){
int temp = leftIndex;
leftIndex=hashMap.get(s.charAt(i))+1; //新leftIndex，因为有重复的，可以直接选择从重复的key的下标+1开始
for(int j =temp;j<leftIndex;j++){
//移除left到i之间存入的key
hashMap.remove(s.charAt(j));
}
rightIndex++;
}else {
rightIndex++;
}
hashMap.put(s.charAt(i),i);
max = Math.max((rightIndex-leftIndex+1),max);
}
return max;
}
}
代码再次优化：
class Solution {
public int lengthOfLongestSubstring(String s) {
// 记录字符上一次出现的位置
int[] last = new int[128];
for(int i = 0; i < 128; i++) {
last[i] = -1;
}
int n = s.length();
int res = 0;
int start = 0; // 窗口开始位置
for(int i = 0; i < n; i++) {
int index = s.charAt(i);
start = Math.max(start, last[index] + 1);
res = Math.max(res, i - start + 1);
last[index] = i;
}
return res;
}
}
该算法把题目中所给的提示信息用上了，字符串为ASCII编码的，并且数组的下标和值都发挥了作用，数组的下标为字符对于的ASCII编码的值，而下标对应的值保存了是从左往右数第几个字符。
或者
class Solution {
public int lengthOfLongestSubstring(String s) {
// 记录字符上一次出现的位置
int[] last = new int[128];
int n = s.length();
int res = 0;
int start = 0; // 窗口开始位置
for(int i = 0; i < n; i++) {
int index = s.charAt(i);
start = Math.max(start, last[index]);
res = Math.max(res, i - start + 1);
last[index] = i+1;
}
return res;
}
}
