无重复字符的最长子串

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

示例 1:

  • 输入: s = “abcabcbb”
  • 输出: 3
  • 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

  • 输入: s = “bbbbb”
  • 输出: 1
  • 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

  • 输入: s = “pwwkew”
  • 输出: 3
  • 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
  • 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

示例 4:

  • 输入: s = “”
  • 输出: 0

解法一: 暴力解法

我采用的是暴力的解法, 复杂度最差 O(n^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
class Solution
{
    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s)
    {
        $len = strlen($s);
        $i = $max = 0;

        for ($j = 0; $j < $len; $j++) {
            for ($k = $i; $k < $j; $k++) {
                if ($s[$k] === $s[$j]) {
                    $i = $k + 1;
                    break;
                }
            }
            if ($j - $i + 1 > $max) {
                $max = $j - $i + 1;
            }
        }

        return $max;
    }
}

运行时间 16ms, 内存 15.2MB

解法二: 哈希表解法

还是那句话, 空间换时间!

未完待续… 下次补..下次补..