第一题 字母异位词分组
题目
文章图片
解题思路
题目线索给到了 排序 和 哈希表
文章图片
排序完成之后可以存入哈希表之中，题目要求的任意顺序返回结果序列刚好与遍历哈希表的特征相符
排序的详细实现
对于字母的排序，我们可以使用sort.Slice函数
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })函数的第一个参数必须为切片，第二个参数为匿名函数，定义排序的规则
代码
func groupAnagrams(strs []string) [][]string {
m := map[string][]string{}
for _, str := range strs {
s := []byte(str)
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
sortedStr := string(s)
m[sortedStr] = append(m[sortedStr], str)
}
ans := make([][]string, 0, len(m))
for _, v := range m {
ans = append(ans, v)
}
return ans
}复杂度分析
时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是O(nklogk)。
空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。
另一种思路
文章图片
第二题 无重复字符的最长子串 题目
文章图片
解题思路
双指针and队列
文章图片
滑动窗口
文章图片
代码
官解
func lengthOfLongestSubstring(s string) int {
// 哈希集合，记录每个字符是否出现过
m := map[byte]int{}
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
rk, ans := -1, 0
for i := 0;
i < len(s);
i++ {
if i != 0 {
// 左指针向右移动一格，移除一个字符
delete(m, s[i-1])
}
for rk + 1 < len(s) && m[s[rk+1]] == 0 {
// 不断地移动右指针
m[s[rk+1]]++
rk++
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1)
}
return ans
}func max(x, y int) int {
if x < y {
return y
}
return x
}优化
func lengthOfLongestSubstring(s string) int {
// 滑动窗口-优化，数组记录每个字符的上一次出现的位置
// 字符由字母、数字、符号、空格组成 ascii->0-127
l, n, cache := 0, len(s), make([]int, 128)
ans := 0
var max func(a,b int) int
max = func(a, b int) int {
if a > b {return a}
return b
}
for i:=0;
i复杂度分析
时间复杂度：O(N)，其中N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
【【golang】leetcode中级-字母异位词分组&无重复字符的最长子串】空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。
推荐阅读
- 彻底理解Golang Map
- kratos线上开源年会它来啦～
- 深入浅出 Golang 资源嵌入方案（go-bindata篇）
- 深入浅出 Golang 资源嵌入方案（前篇）
- golang 经典案例总结
- Go实战 | 基于有向无环图的并发执行流的实现
- Golang 数组和切片
- Go JSON编码与解码（）
- golang map基础知识