网站首页 返回列表
像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

leetcode基础算法学习之LongestSubstr

23-10-22 10:08:40 字节波 340

### 习题三：
给定一个字符串，找到不重复字符的最长子字符串的长度。
Input: `abcabcbb`
Output: `3`
Explanation: 找到答案`abc`, 长度为`3`
Input: `bbbbb`
Output: `1`
Explanation: 找到答案`b`, 长度为`1`
Input: `pwwkew`
Output: `3`
Explanation: 找到答案`wke`, 长度为`3`
注意：这里是最长子字符串，而不是最长子序列。如果是最长子序列应该是`pwke`

### 方法一：暴力
仍然采取由简入繁的方式来逐步寻找思路，首先第一解题的感觉肯定是逐个检查所有子字符串，看它是否没有重复的字符。这也是最笨的方法，不过还是用这方法先解一下：

```go
package main

import (
	"math"
	"fmt"
)

func lengthOfLongestSubstring1(s string) int  {
	n := len(s)
	ans := float64(0)
	for i := 0; i < n; i++ {
		for j := i + 1; j <= n; j++ {
			if allUnique(s, i, j) {
				ans = math.Max(ans, float64(j - i))
			}
		}
	}
	return int(ans)
}

func allUnique(s string, start int, end int) bool {
	h_table := map[string]int{}
	for i := start; i < end; i++ {
		ch := string(s[i])
		if _, ok := h_table[ch]; ok {
			return false
		}
		h_table[ch] = i
	}
	return true
}

func main() {
	fmt.Println(lengthOfLongestSubstring2("abcabcbb"))
	fmt.Println(lengthOfLongestSubstring2("bbbbb"))
	fmt.Println(lengthOfLongestSubstring2("pwwkew"))
}
```
输出：
```go
3
1
3
```
用最笨的方法，可以简单得到想要的答案，可该方法很明显可以看出时间复杂度为n³（2次for循环，1次allUnique判断）。因此，肯定不是最有效率的办法。

### 方法二：滑动窗口
再来分析一下，我们反复检查一个子字符串，看它是否有重复的字符，这显然是不必要的，假设有1个子字符串为s[i:j-1]是不存在重复字符串的，我们仅需要检查s[j]是否在s[i:j-1]中就可以了，这种方法是我们在字符串或数组等问题中常用的1种抽象概念并命名为滑动窗口。另外我们检查是否有重复字符串时，也完全不需要扫描子字符串，我们可以使用map来检查当前需要查询的字符串，从这两点出发，理应会提高很多效率。
```go
package main

import (
	"fmt"
	"math"
)

func lengthOfLongestSubstring2(s string) int  {
	n := len(s)
	h_table := map[string]int{}
	ans := float64(0)
	i, j := 0, 0
	for i < n && j < n {
		if _, ok := h_table[string(s[j])]; !ok {
			h_table[string(s[j])] = i
			j++
			ans = math.Max(ans, float64(j - i))
		} else {
			delete(h_table, string(s[i]))
			i++
		}
	}
	return int(ans)
}

func main() {
	fmt.Println(lengthOfLongestSubstring2("abcabcbb"))
	fmt.Println(lengthOfLongestSubstring2("bbbbb"))
	fmt.Println(lengthOfLongestSubstring2("pwwkew"))
}
```
输出：
```go
3
1
3
```
代码中可以看出，时间复杂度为n-2n，在最坏的情况下，每个角色将被访问2次i和j。

### 方法三：
我们还可以再度优化，让时间复杂度降低到n，我们可以将map的key和value分别映射为字符和字符索引，当找到重复字符时，可以立即跳过字符。
```go
package main

import (
	"fmt"
	"math"
)

func lengthOfLongestSubstring3(s string) int  {
	n := len(s)
	h_table := map[string]int{}
	ans := float64(0)
	for j, i := 0, 0; j < n; j++ {
		if key, ok := h_table[string(s[j])]; ok {
			i = int(math.Max(float64(key), float64(i)))
		}
		ans = math.Max(ans, float64(j - i + 1))
		h_table[string(s[j])] = j + 1
	}
	return int(ans)
}

func main() {
	fmt.Println(lengthOfLongestSubstring3("abcabcbb"))
	fmt.Println(lengthOfLongestSubstring3("bbbbb"))
	fmt.Println(lengthOfLongestSubstring3("pwwkew"))
}
```
输出：
```go
3
1
3
```

### 方法四：
前面我们已经做的很好了，时间复杂度已经降到了n，可前面的实现都没有对s的字符串的字符集进行假设，如果我们知道charset相当小，我们可以利用整数数组来代替直接访问map，数组的索引及代表字符集中的某个字符。
常用的字符集数组有：
- [26]int{} 用于字母`a-z`或`A-Z`
- [128]int{} 用于`ASCII`
- [256]int{} 用于`扩展ASCII`

```go
package main

import (
	"fmt"
	"math"
)

func lengthOfLongestSubstring4(s string) int  {
	n := len(s)
	h_table := [128]int{}
	ans := float64(0)
	for j, i := 0, 0; j < n; j++ {
		i = int(math.Max(float64(h_table[s[j]]), float64(i)))
		ans = math.Max(ans, float64(j - i + 1))
		h_table[s[j]] = j + 1
	}
	return int(ans)
}

func main() {
	fmt.Println(lengthOfLongestSubstring4("abcabcbb"))
	fmt.Println(lengthOfLongestSubstring4("bbbbb"))
	fmt.Println(lengthOfLongestSubstring4("pwwkew"))
}
```
输出：
```go
3
1
3
```
时间复杂度与方法3一致，但在另一标准**空间复杂度**上明显要更低一些。

### 习题小结
本节重点是巧妙利用滑动窗口概念来处理字符串等效率问题，并大致了解一下空间复杂度是一个什么概念。

关键字词[算法]

分享到：

上一篇：leetcode基础算法学习之addTwoNumbers

下一篇：leetcode基础算法学习之ReverseInt

如需留言，请登录，没有账号？请注册

0 条评论 0 人参与