【GoLang】【算法模板】2、GoLang 算法模板整理

0、前言

整理一下 golang 的算法板子，作为备忘录使用。可能有些板子、博文是引用互联网博主的，会注明出处，在此多蟹…

1、GoLang 算法必会技巧

1.1、标准库

1.1.1、sort 包

引用：

• 其他博主： [Go语言tips01]浅谈sort包
• 官方库 Go1.24.0-sort

---

例题：

• [M二分] lc34. 在排序数组中查找元素的第一个和最后一个位置(二分+经典)
  [M二分] lc2080. 区间内查询数字的频率(模拟+二分+数据结构+Go二分库函数+知识总结)
  • sort.SearchInts 练习掌握

1.1.2、slice 包

引用：

• 官方库 Go1.24.0-slice

---

例题：

• lc 灵神 —【视频讲解】二分查找总是写不对？三种写法，一个视频讲透！（Python/Java/C++/C/Go/JS）
  
  • slices.BinarySearch

1.2、数据结构

1.2.1、优先队列

堆这块，日后补，大根堆、小根堆啥的

2、板子

2.1、二分

整数二分、浮点数二分：

• 其他博主： [Go语言tips01]浅谈sort包
• 官方库 Go1.24.0-sort
  • sort.SearchInts 系列函数

---

2.1.1、lower_bound、upper_bound

• [M二分] lc2080. 区间内查询数字的频率(模拟+二分+数据结构+Go二分库函数+知识总结)

func upperBound(pos []int, target int) int {l, r := 0, len(pos)-1for l <= r {mid := l + (r - l) / 2if pos[mid] <= target {l = mid + 1} else {r = mid - 1}}return l
}func lowerBound(pos []int, target int) int {l, r := 0, len(pos) - 1for l <= r {mid := l + (r - l) / 2if pos[mid] < target {l = mid + 1} else {r = mid - 1}}return l
}

---

2.2、字符串

2.2.1、kmp

知识点：

• [kmp+模板] kmp模板
• 哔站讲的非常好的一个老师 - - - 懒猫老师-数据结构-(14)字符串匹配-KMP算法1(模式匹配)

---

注意：

• strstr() 函数，其时间复杂度是 $O(n\ast m)$ 的，这也是为什么工程业务上，不要随便使用的原因。
• kmp 函数，其时间复杂度是 $O(n+m)$ 的。性能大大提升。

---

模板题：

• [Ekmp] lc28. 实现 strStr()(kmp+字符串哈希)

进阶题：

• [kmp] aw141. 周期(kmp循环节+模板题)

---

以：[Ekmp] lc28. 实现 strStr()(kmp+字符串哈希) 为例题。

这里将 kmp 板子稍微改良了下，固定返回一个 []int，且必定有元素：

• 一个元素
  • 为 -1 时，说明没有匹配。
  • 不为 -1 时，为正常的在 s 串中的第一次匹配下标位置。
• 多个元素
  • s 串与 p 串有多个匹配子串，为 这些位置的 s 串下标位置。

---

细节：

• s、p 都需要添加 左哨兵，为空字符串。
• ne 数组求解时，i 需要从 i=2 开始匹配。

func getNe(p string) []int {m := len(p)ne := make([]int, m + 1)p = " " + p// 注意，这里 i 需要从实际的第二个字符开始才对，// 从第一个字符开始时 p[i] == p[j+1] --》p[1]=p[0+1] 将成立，并不是一个严格的当前字符相等的关系// 建立的 ne 数组就是错误的for i, j := 2, 0; i <= m; i ++ {  for j > 0 && p[i] != p[j + 1] {j = ne[j]}if p[i] == p[j + 1] {j ++ }ne[i] = j}return ne
}// 返回所有 s, p 串中的匹配下标构成的切片，如果不匹配，则返回元素为 -1 的切片
// in: s: "sadbutsad"   p: "sad"
// out: [0, 6]
// in: s: "leetcode"   p: "leeto"
// out: [-1]
func kmp(s, p string) []int {ne := getNe(p)n, m := len(s), len(p)s, p = " " + s, " " + pmatchs := []int{}for i, j := 1, 0; i <= n; i ++ {for j > 0 && s[i] != p[j + 1] {j = ne[j]}if s[i] == p[j + 1] {j ++ }if j == m {matchs = append(matchs, i - m)j = ne[j]         // 现在已经找到匹配位置了。下一次开始匹配，j 直接跳 ne 数组即可}}if len(matchs) == 0 {return []int{-1}}return matchs
}func strStr(s string, p string) int {return kmp(s, p)[0]
}