3.无重复字符的最长子串

发表于 | 更新于 | 分类于 | | 阅读次数：
本文字数： 7.5k | 阅读时长 ≈ 7 分钟

一、题目原型：

给定一个字符串，找出不含有重复字符的最长子串的长度。

二、题目意思剖析：

1
2
3
4
5
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。

给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。

给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列  而不是子串。

三、解题思路：

3.1暴力破解

1
2
3
4
5
6
7
8
9
10
// 分析
// abcabcdb
//    abcd -- 答案
a          b           c            a           b
ab         bc          ca           ab          bc
abc  3     bca  3      cab  3       abc         bcd  3
abca ❌    bcab ❌    cabc ❌      abcd  4     bcdb  ❌
                                    abcdb ❌
// 1.找出每次遍历时当前string的最长substring，当然不能出现重复的字母
// 2.从中拿到最长的
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
// 上代码
// 注：resultLength是个全局变量
func lengthOfLongestSubstring(_ s: String) -> Int {
    
    if s.count <= 1 {
        print(s)
        return s.count
    }
    
    var letters: [Character] = []
    for char in s {
        letters .append(char)
    }
      print(letters)
    
    var subString: String = ""
    var maxLength: Int = 1
    for i in 0..<letters.count - 1 {
        
        subString .append(letters[i])
        for j in i+1..<letters.count {
            if !subString .contains(letters[j]) {
                subString .append(letters[j])
                maxLength = maxLength + 1
                // 用全局变量resultLength保存最大的长度
                resultLength = maxLength > resultLength ? maxLength : resultLength
            }else {
                  print(subString)
                  print(maxLength)
                // 用全局变量resultLength保存最大的长度
                resultLength = maxLength > resultLength ? maxLength : resultLength
                subString .removeAll()
                maxLength = 1
                break
            }
        }
        
        // 如果 resultLength和i 相加刚好等于letters.count - 1，就不需要再进行下面的遍历了。
        // 因为此时的resultLength的长度是最长的了
        if i + resultLength == (letters.count - 1) {
            break
        }
    }
    return resultLength
}

3.2滑动窗口

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
func lengthOfLongestSubstring(_ s: String) -> Int {
    let n = s.count
    var letters: [String] = []
    for char in s {
        let tempStr: String = String.init(char)
        letters .append(tempStr)
    }
    // 1.如果s长度 <= 1
    if s.count <= 1 {
        print(s)
        return s.count
    }
    var set: [String] = Array.init(repeating: "", count: letters.count)
    var start: Int = 0 // 起始位置
    var end: Int = 0   // 结束位置
    var maxLength: Int = 0  // 最大长度
    while start<n && end<n {
        maxLength = (end - start + 1) > maxLength ? (end - start + 1) : maxLength
        if set.contains(letters[end]) {
            let index: Int = set.index(of: letters[end])!
            // 1.start移动到上次出现重复位置的后一位
            start = index + 1
            // 2.短遍历，将前面遍历完的字符串置为空
            for i in tempStart..<start {
                if set[i] != "" {
                    set[i] = ""
                }
            }
            // 3.tempStart作用：记录上一次start位置
            tempStart = start
            // 4.当发现重复字符，maxLength需要-1
            maxLength = maxLength - 1
        }
        set[end] = letters[end]
        end = end + 1
        print("start-\(start) end-\(end) maxLength-\(maxLength)")
        // 最终最大长度
        resultLength = maxLength > resultLength ? maxLength : resultLength
    }
    return resultLength
}

四、小结

暴力破解：时间复杂度o(n的平方)
滑动窗口：时间复杂度o(n*一个常数)
滑动窗口参考资料，这里边有详细图解

由于时间复杂度太高了，没有通过leetcode检测，超时了。😭

1
2
3
4
5
// leetcode测试用例
var s:String = ""
for _ in 0..<100 {
    s .append("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ ")
}

不同区间的耗时统计:
0..<10 - 284ms
0..<20 - 960ms
0..<50 - 5.7s
0..<100 - 20s

ps：当区间为[0,100]，耗时简直恐怖。。。

—————————————分割线————————————-
经过多方查找，和自己验证，果断找到了一种办法。

用hash值。

因为每个字符只对应一个hash值。但是swift的这个值和c++或者java又有所不同。他们之间的差值不同。

验证:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
将所有字符都列出来，比较找出最大最小的hash值和对应的字符。
var s:String = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ "
var characters:[String] = []
for char in s {
    let string:String = String.init(char)
    characters.append(string)
}
var max: Int = 0
var min: Int = Int.max
for i in 0..<characters.count {
    if (characters[i].hashValue > max) {
        max = characters[i].hashValue
        print("max:\(max), characters[i]:\(characters[i]) ,i:\(i)")
    }
    if (characters[i].hashValue < min) {
        min = characters[i].hashValue
        print("min:\(min), characters[i]:\(characters[i]) ,i:\(i)")
    }
}

结果：
max: I 4799450059485597695
min: _ 4799450059485595649
差值：2046

然后就简单了，之前一直卡在越界问题上

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
func lengthOfLongestSubstring(_ s: String) -> Int {
    
    var last:[Int] = Array.init(repeating: -1, count: 2047)
    var start: Int = 0 // 起始位置
    var maxLength: Int = 0  // 最大长度
    var characters:[String] = []
    
    for char in s {
        let string:String = String.init(char)
        characters.append(string)
    }
    
    for i in 0..<characters.count {
        
        let hash_i: Int = characters[i].hashValue
        let hash_a: Int = "_".hashValue
        
        if (last[hash_i - hash_a] >= start) {
            maxLength = max(maxLength, i-start)
            start = last[hash_i - hash_a] + 1
        }
        last[hash_i - hash_a] = i
    }
    maxLength = max(maxLength, s.count - start)
    return maxLength
}

奇迹出现：耗时6ms！几千倍的差距。

然而leetcode还是没通过，说我越界了，我特么。。。自己运行没问题啊

然后我申诉了该题目。😏

—————————————分割线————————————-

在做387.字符串中的第一个唯一字符时，我发现了如果用hash值是会越界的，在leetcode上是会这样。那我们可以用ASCII码来搞，因为每一个字符只对应一个ASCII码。
可以参照ASCII码对照表

1
2
3
4
5
6
7
8
9
abcdefghijklmnopqrstuvwxyz   97~122
ABCDEFGHIJKLMNOPQRSTUVWXYZ   65~90
0123456789                   48~57
!\"#$%&'()*+,-./             33~47
:;<=>?                       58~64
@[\\]^_`                     91~96
{|}~                         123~126
" "                          32
空字符                        0

接下来，只要把hashValue换一下就OK了。

1
2
3
4
5
6
// 所有字符的所对应的ASCII码，用CChar类型表示，实质为Int8类型。
// 该方法末尾会默认加上一个"0"元素，也就是空字符
var allCharacter: [Int8]? =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ ".cString(using: String.Encoding.utf8)
print(allCharacter)
print(allCharacter?.count)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func lengthOfLongestSubstring(_ s: String) -> Int {
    
    var last:[Int] = Array.init(repeating: -1, count: 127)
    var start: Int = 0 // 起始位置
    var maxLength: Int = 0  // 最大长度
    
    let chars: [Int8]? = s.cString(using: String.Encoding.utf8)
    
    for i in 0..<s.count {
        
        let hash_i: Int = Int(chars![i])
        let hash_null: Int = 0
        
        if (last[hash_i - hash_null] >= start) {
            maxLength = max(maxLength, i-start)
            start = last[hash_i - hash_null] + 1
        }
        last[hash_i - hash_null] = i
    }
    maxLength = max(maxLength, s.count - start)
    return maxLength
}

后记

这一题和387.字符串中的第一个唯一字符思路大致相同，不太清楚的可以先看一下那题。
1.耗时44毫秒，超过99.35%的提交记录，总提交数987。

这一题总算告一段落了。
大家有疑惑的地方欢迎一起探讨啊。😄

坚持原创技术分享，您的支持将鼓励我继续创作！