「リートコード - 3. Longest Substring Without Repeating Characters」

发表于 | 分类于

ジャバソリューション

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        int n = s.length();
        if (n == 0 || n == 1) {
            return n;
        }
        HashMap<Character, Boolean> have = new HashMap<Character, Boolean>();
        for (int i = 0; i < n; ++i) {
            have.put(s.charAt(i), false);
        }
        int u = 0, v = 0;
        have.put(s.charAt(0), true);
        while (v + 1 < n && !have.get(s.charAt(v + 1))) {
            ++v;
            have.put(s.charAt(v), true);
        }
        int res = v + 1;
        boolean test = false;
        while (v < n - 1) {
            ++v;
            while (!have.get(s.charAt(v)) && v + 1 < n) {
                have.put(s.charAt(v), true);
                ++v;
            }
            res = Math.max(res, v - u);
            if (test) {
                System.out.println(res + ", " + u + ", " + v);
            }
            if (v == n - 1 && !have.get(s.charAt(v))) {
                res = Math.max(res, v - u + 1);
                if (test) {
                    System.out.println(res + ", " + u + ", " + v);
                }
                break;
            }
            while(s.charAt(u) != s.charAt(v)) {
                have.put(s.charAt(u), false);
                ++u;
            }
            ++u;
            res = Math.max(res, v - u + 1);
            if (test) {
                System.out.println(res + ", " + u + ", " + v);
            }
        }
        return res;
    }
}

其实写的时候已经意识到是很累赘的写法了，看了题解其实可以很轻松解决，不过考虑本来复杂度肯定最优还是写完了，然后学习一波。