這里主要是用到一個(gè)移動(dòng)窗口的概念洋只。窗口移動(dòng)要解決的問(wèn)題則是
如果當(dāng)前的字符已經(jīng)重復(fù)了阻肿。那么接下來(lái)我的窗口的起始位置應(yīng)該放在哪玖像。
也就是說(shuō)摄欲，我們需要記錄一個(gè)字符和他重復(fù)時(shí)下一個(gè)起始位置的對(duì)應(yīng)關(guān)系郑趁。
一個(gè)例子
這里用一個(gè) nextBeginPos[128]來(lái)記錄對(duì)應(yīng)字符重復(fù)時(shí)的下一個(gè)起始位置刊驴。
每次算當(dāng)前窗口長(zhǎng)度的時(shí)候用 end - begin + 1, 然后和當(dāng)前的 maxLength 比較。如果比他大寡润，則用 end - begin + 1;
LeetCode3無(wú)重復(fù)最長(zhǎng)子串.jpg
image.png
public class LongestSubString {
public static int longest(String s) {
int maxLength = 0;
int[] nextBeginPos = new int[128];
for (int begin = 0, end = 0; end < s.length(); end++) {
begin = nextBeginPos[s.charAt(end)] > begin ? nextBeginPos[s.charAt(end)] : begin;
maxLength = maxLength > end - begin + 1 ? maxLength : end - begin + 1;
nextBeginPos[s.charAt(end)] = end + 1;
}
return maxLength;
}
public static void main(String[] args ) {
System.out.println(longest("abcabcbb"));
}
}
