无重复字符的最长子串

在这里插入图片描述

解题思路

这道题我们可以把问题想象成这样：

用两个指针l和r圈定一个窗口，这个窗口内始终保持没有重复字符，然后让这个窗口在字符串上不断滑动。

具体来说，右指针r不断向右扩展窗口，每次遇到一个新字符时，先检查这个字符之前是否在窗口内出现过，如果出现过，就把左指针l移动到那个重复字符的下一个位置，这样就保证了窗口内永远没有重复字符。

在这个过程中，我们持续记录窗口的最大长度，最后得到的就是答案。

举个栗子

输入: “abcabcbb”

r=0时,‘a’首次出现,窗口[a],长度=1
r=1时,‘b’首次出现,窗口[ab],长度=2
r=2时,‘c’首次出现,窗口[abc],长度=3
r=3时,‘a’重复,l移到位置1,窗口[bca],长度=3
r=4时,‘b’重复,l移到位置2,窗口[cab],长度=3
r=5时,‘c’重复,l移到位置3,窗口[abc],长度=3
r=6时,‘b’重复,l移到位置5,窗口[cb],长度=2
r=7时,‘b’重复,l移到位置7,窗口[b],长度=1

输出: 3 (最长子串为"abc")

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public static int lengthOfLongestSubstring(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    // 记录每个字符上次出现的位置
    int[] last = new int[256];
    // 初始化所有字符都没有出现过
    Arrays.fill(last, -1);
    // 记录最长子串长度
    int ans = 0;
    
    for (int l = 0, r = 0; r < n; r++) {
        // 如果当前字符之前出现过,移动左指针到重复位置的下一位
        l = Math.max(l, last[s[r]] + 1);
        // 更新最长长度
        ans = Math.max(ans, r - l + 1);
        // 记录当前字符的位置
        last[s[r]] = r;
    }
    return ans;
}

如果觉得有帮助，欢迎点赞、关注、转发~