剑指offer（第二版）面试题48：最长不含重复字符的子字符串（Java）

淩亂°似流年 2021-11-06 00:12 182阅读 0赞

### 题目 ###

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含从’a’到’z’的字符。例如，在字符串中”arabcacfr”，最长非重复子字符串为”acfr”，长度为4。

### 解题思路 ###

动态规划思想

通过一个额外数组存储出现过字符的地址，数组默认为0，额外变量Max记录最长不重复子字符串长度，len积累当前子字符串长度。分两种情况：

1）当第一次出现，记录当前位置，长度len++；

2）非第一次出现，计算就与上一次出现位置距离，分为两种情况：

a）当超过当前最长子字符串Max则意味该字符已经被当前记录刷新，则len++；

b）若未超过则刷新len为该字符前一次出现之后的字符到当前字符长度。

代码如下：

import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()) {
            	int[] x = new int[26];
            	String str = sc.next();
            	int len = 0;
            	int max = 0;
            	for(int i=0;i<str.length();i++) {
            		int n = Integer.valueOf(str.charAt(i)-'a');
            	
            		if(x[n]!=0) {
            			if(i-x[n]+1<=max)
            				len = i-x[n]+1;
            			else
            				len++;
            			x[n]=i+1;
            			if(max<len) {
            				max=len;
            			}
            		}else {
            			x[n]=i+1;
            			len++;
            			if(max<len) {
            				max=len;
            			}
            		}
            	}
            	System.out.println(max);
            }
            
        }
    }