一、题目原型：
给定一个字符串，找出不含有重复字符的最长子串的长度。
二、题目意思剖析：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。
三、解题思路：
3.1暴力破解
// 分析
// 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.从中拿到最长的
// 上代码
// 注：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滑动窗口
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检测，超时了。😭
// 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又有所不同。他们之间的差值不同。
验证:
将所有字符都列出来，比较找出最大最小的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
然后就简单了，之前一直卡在越界问题上
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码对照表
abcdefghijklmnopqrstuvwxyz 97~122
ABCDEFGHIJKLMNOPQRSTUVWXYZ 65~90
0123456789 48~57
!\"#$%&'()*+,-./ 33~47
:;<=>? 58~64
@[\\]^_` 91~96
{|}~ 123~126
" " 32
空字符 0
接下来，只要把hashValue换一下就OK了。
// 所有字符的所对应的ASCII码，用CChar类型表示，实质为Int8类型。
// 该方法末尾会默认加上一个"0"元素，也就是空字符
var allCharacter: [Int8]? =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ ".cString(using: String.Encoding.utf8)
print(allCharacter)
print(allCharacter?.count)
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
}
func lengthOfLongestSubstring(_ s: String) -> Int {
// 数组长度是127
// 因为根据ASCII码可以看出，所有字符的ASCII码最小为0(空字符)，最大为126(~)
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])
if (last[hash_i] >= start) {
maxLength = max(maxLength, i-start)
start = last[hash_i] + 1
}
last[hash_i] = i
}
// 当跳出循环时，需要判断再判断一次，因为可能从start字符串最后的那一段，比maxLength要大。
// 比如 s = "xy812~678"
// 无重复最长的串 = 12~678
maxLength = max(maxLength, s.count - start)
return maxLength
}
思考
更新于 2019-11
题目只是求最长子串的长度，我想既然能拿到长度，那么我们怎么顺便把子串也同时打印出来。
想来想去，只能通过start和end指针的滑动窗口那个方案。
// 需要定义几个全局变量
var resultLength: Int = 0
var resultStart: Int = 0
var resultEnd: Int = 0
var tempStart: Int = 0
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) : maxL
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) - \(end) - \(maxLength)")
// 最终最大长度
resultLength = maxLength > resultLength ? maxLength : resultLength
if (resultLength < maxLength) { // 如果最大长度改变了，更新resultLength，
resultStart = start
resultEnd = end - 1
resultLength = maxLength
}
print("\(resultStart) - \(resultEnd) - \(resultLength)")
print("----------------------")
}
print(s)
var subString : String = ""
for i in resultStart...resultEnd {
subString.append(letters[i])
}
// 最长无重复子串
print(subString)
print("----------------------")
return resultLength
}
后记
这一题和387.字符串中的第一个唯一字符思路大致相同，不太清楚的可以先看一下那题。
1.耗时44毫秒，超过99.35%的提交记录，总提交数987。
这一题总算告一段落了。
大家有疑惑的地方欢迎一起探讨啊。😄
