题目：输入一个字符串，找出字符串中最长的不含重复字符的子字符串，计算该子字符串的长度。假设字符串中的字符为“a~z”，例如 arabcacfr ，最长的字符串为 rabc 和 acfr ，长度为 4 。————源自《剑指0ffer》
思路：采用暴力的方法，时间复杂度高度 n^3 ,显然是不可取的。
本题应该采用动态规划的方法来解决，时间复杂度只需要 n ,以及一个辅助的数组即可。
我们直接以 arabcacfr 为例子进行分析，从头开始遍历字符串的字符。
1.第一个字符 a ，此前 a 没有出现过，所以长度为 f(1) = 1，最长的子字符串是 a ;
2.第二个字符 r ，同样没出现过，所以 f(1) = 2 ,最长的子字符串是 ar ;
3.第三个字符 a ,因为 在第一个已经出现过了，且 在当前的最长字符串 ar 中，所以现在 f(2) = 2,最长子字符串更新为 ra；
4.第四个字符 b ,f（3） = 3，第五个字符 c ,f（4） = 4 ,此时最长子字符串为 rabc ；
5.第六个字符 a,在我们当前的最长子字符串中已经出现，所以 f（5） = 3，最长子字符串更新为 bca ;
6.第七个字符c,类似上面，所以 f（6） = 2，最长子字符串为 ac ;
7.第八个字符 f,没出现过 所以 f（7） = 3，最长子字符串更新为 acf
8.最后 一个字符 r，前面已经出现过，但是不在我们当前最长子字符串acf 中，所以 f（8） = 4，最长子字符串更新为acfr 。
分析到此结束，接下来我们如何去实现？这就需要我们用到前面说的辅助数组 arr，我们用一个初始化的值全为负数的数组，以字符串中的字符temp 为下标进行标记，数组的值为该字符的位置 i 。当我们遍历到第 i 个字符，如果
arr[ temp ] 的值为负数，那么说明这个字符还未出现过，如果 arr[ temp ] 值不为负数，那么说明这个字符已经出现过，接下来我们要判断这个字符是否在我们当前统计的最长子字符串中。如果不在当前的子字符串中，那么 f( i） = f（i - 1）+ 1；如果在当前的最长子字符串中，就像上面的第4 、 5步，我们需要重新计算当前最长子字符串，也就是需要找到上一次出现该字符的位置，然后从它后面一位开始统计。具体的代码：
package com.hunter.Offer_Example; import java.util.Scanner; /** * 最长的没有重复的子字符串 * @author luzi * */ public class longestNotRepeatSubStr { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan = new Scanner(System.in); while(scan.hasNext()){ String str = scan.next(); System.out.println(getLongestSubStr(str)); } } private static int getLongestSubStr(String str) { // TODO Auto-generated method stub if(str == null) return 0; int[] arr = new int[26]; int max = 0; int count = 0; for(int i = 0; i < 26; i++){ arr[i] = -1; } for(int i = 0; i < str.length(); i++){ if(arr[str.charAt(i) - 'a'] == -1){ arr[str.charAt(i) - 'a'] = i; count++; } else if(arr[str.charAt(i)] != -1){ //说明当前的字符str.charAt(i)上一次出现的位置在现在统计的子字符串前面，，对现在的统计没影响 if(i - arr[str.charAt(i) - 'a'] > count){ count++; } //当前字符上一次出现的位置在统计之中，我们需要重新统计count即当前的最长子字符串 else{ count = i - arr[str.charAt(i) - 'a']; } //更新当前字符的位置 arr[str.charAt(i) - 'a'] = i; } if(count >= max) max = count; } return max; } }
因为题目中说明 字符在 a~z 之间，所以我们只需要一个 长度为 26 的数组，但是如果将字符扩大到所以的ASCII码，那就需要一个长度为 127 的数组，并且将
arr[str.charAt(i) - 'a'] 改为 arr[str.charAt(i)]
