IOS 算法(中级篇) ----- 无重复字符的最长子串

给定一个字符串 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 算法合集地址