给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
例子
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
输入: s = ""
输出: 0
方法1.遍历法+自带函数
题意稍微解释下, 找到给定字符串中最长, 不含重复字母子串
以"abcabcbb"举例, 例如:
① "a", "b", "c", "ab", "bc"...连续的都为子串, 像"abb"这种不为子串
② "a", "b", "c", "ab", "bc"为子串, 但都不是最长, 所以不满足
③ "abca"也为子串, 也很长, 但含重复字母a, 固也不满足条件
④ "abc", "bca", "cab", 这种最长且不含重复字母满足条件
解题思路
利用 遍历法 + swift自带函数解题
定义一个容器数组存储每次遍历的字符, 如果包含则删除数组内包含之前所有元素
找当前与之前最大取最大即可
以"abcabcbb"举例
- 第一次, |a|bcabcbb
结果: ["a"], 最大1
- 第二次, a|b|cabcbb
结果: ["a", "b"], 最大2
- 第三次, ab|c|abcbb
结果: ["a", "b", "c"], 最大3
- 第四次, abc|a|bcbb
结果: ["b", "c", "a"], 最大3; 删除数组中a之前所有元素, 比最大
- 第五次, abca|b|cbb
结果: ["c", "a", "b"], 最大3; 删除数组中b之前所有元素, 比最大
- 第六次, abcab|c|bb
结果: ["a", "b", "c"], 最大3; 删除数组中c之前所有元素, 比最大
- 第七次, abcabc|b|b
结果: ["c", "b"], 最大3; 删除数组中b之前所有元素, 比最大
- 第八次, abcabcb|b|
结果: ["b"], 最大3; 删除数组中b之前所有元素, 比最大
那么有
未翻译版
class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
var res = 0, arr = [Character]()
for c in s {
if let index = arr.firstIndex(of: c) {
arr.removeFirst(index + 1)
}
arr.append(c)
res = max(arr.count, res)
}
return res
}
}
翻译版
class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
// 定义容器数组arrarr, 最后结果res
var res = 0, arr = [Character]()
// 遍历s中字符
for c in s {
// 如果数组中包含当前元素, 删除当前以及之前元素
// firstIndex, removeFirst官方解释在下面
if let index = arr.firstIndex(of: c) {
arr.removeFirst(index + 1)
}
// 如果数组中包含当前元素, 删除重复元素之前的所有元素
arr.append(c)
// 取最大
res = max(arr.count, res)
}
// 返回结果
return res
}
}
firstIndex:
firstIndex官方解释
removeFirst
removeFirst官方解释
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
