面试题16：不含重复字符的最长子字符串（Java版）_s='abcca'的串长度

题目：输入一个字符串，求该字符串中不含重复字符的最长子 字符串的长度。例如，输入字符串"babcca"，其最长的不含重复字符的子字符串是"abc"，长度为3。

// 用两个指针来指向子字符串的最左边和最右边
// 通过移动两个指针来找到不包含重复字符的字符串
// 当字符串不重复时将右边的指针往右移动增加子字符串的长度
// 当子字符串中字符重复时将左边的指针往右移动直到两个指针
// 之间的子字符串中无重复字符为止counts长度为128的一个哈希表
// 因为ASCII码最多表示128个数，将字符的ASCII码作为counts数组的索引
// 值作为字符出现的次数
public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) {
        return 0;
    }
    int[] counts = new int[128];
    int i = 0;
    int j = -1;
    int longest = 1;
    for (; i < s.length(); i++) {
        counts[s.charAt(i)]++;
        // 当子字符串中字符重复时左指针右移
        while (hasGreaterThan1(counts)) {
            j++;
            // 左指针右移后因为子字符串长度减少所以对应
            // 的减少的字符在counts数组中的数量也减一
            counts[s.charAt(j)]--;
        }
        longest = Math.max(i - j, longest);
    }
    return longest;
}

// 方法一：如果counts数组中有数的值大于1则代表有子字符串有重复字符
private boolean hasGreaterThan1(int[] counts) {
    for (int count : counts) {
        if (count > 1) {
            return true;
        }
    }
    return false;
}

// 方法二：直接通过一个变量countDup来判断子字符串是否含有重复字符
// 这种方式可以避免每次都遍历counts数组而造成的大量的冗余的循环判断
public int lengthOfLongestSubstring2(String s) {
    if (s.length() == 0) {
        return 0;
    }
    int[] counts = new int[128];
    int i = 0;
    int j = -1;
    int longest = 1;
    int countDup = 0;
    for (; i < s.length(); i++) {
        counts[s.charAt(i)]++;
        // 当counts[s.charAt(i)] == 2则代表一个字符在子字符串中出现了两次
        // 因此将countDup的值加一
        if (counts[s.charAt(i)] == 2) {
            countDup++;
        }
        // 当countDup == 1 则说明子字符串中有重复的字符
        // 因此左指针反复右移直到子字符串中无重复字符
        while (countDup == 1) {
            j++;
            counts[s.charAt(j)]--;
            if (counts[s.charAt(i)] == 1) {
                countDup--;
            }
        }
        longest = Math.max(i - j, longest);
    }
    return longest;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70