Go：常见算法题的工程价值，双指针、滑动窗口、哈希、递归、回溯怎么理解

发表于 分类于 本文字数： 6.1k 阅读时长 ≈ 22 分钟
Go 里的双指针、滑动窗口、哈希、递归、回溯，如果只停在题解层面，很快就会和项目脱节。这篇文章围绕一个巡检失败分析与补救计划器，讲清这些模式在合并数据、连续区间分析、去重索引、依赖遍历和资源受限决策里的真实工程价值。

提到算法，最容易出现的偏差通常是两种：

  • 一种是把它当成面试题，写完题解就结束
  • 另一种是觉得业务代码里只需要会调库，算法没有实际价值

真正开始写 Go 服务、任务执行器、巡检系统、日志分析工具之后，这几类模式会反复出现，只是名字不一定直接写在代码旁边：

  • 两份有序结果合并去重，常见是双指针
  • 一段连续时间里的异常峰值分析，常见是滑动窗口
  • 去重、聚合、索引、快速判断是否出现过，常见是哈希
  • 树形依赖、目录扫描、层级配置遍历，常见是递归
  • 在预算、时间、容量受限时挑一组最优动作，常见是回溯

这一篇不按 LeetCode 题号来讲，而是直接围绕一个实际场景展开：做一个巡检失败分析与补救计划器。

这个工具要做五件事：

  1. 收集多路巡检结果并去重
  2. 合并两份已排序的失败服务列表
  3. 找出 10 分钟内失败最密集的窗口
  4. 递归展开服务依赖树，找出受影响范围
  5. 在补救预算受限时，枚举一组收益更高的补救动作

这条链路足够小，能把五种模式串在一起；也足够真实，能看清它们在工程里到底解决什么问题。

一、这篇文章要解决什么问题

读完这一篇，应该能独立回答这些问题：

  1. 双指针、滑动窗口、哈希、递归、回溯分别适合哪类工程问题
  2. 为什么这些模式的价值不在“会不会背模板”，而在“能不能看出数据流特征”
  3. Go 里写这些模式时，最常见的错误是什么
  4. 什么时候该优先用简单写法，什么时候该上模式化解法
  5. 这些模式怎么写成可测试、可排障、可维护的代码

如果这些问题能答清，后面写日志处理、任务编排、故障分析、资源调度、测试工具时，代码会稳很多。

二、先把一句话结论说清楚

这些算法模式真正有价值的地方，不是“做题时能过”，而是：

当数据是有顺序的、连续的、可索引的、层级化的、或者要在约束下做选择时，它们能把复杂度和代码结构一起压下来。

更具体一点：

  • 双指针解决的是“两个位置如何协同前进”
  • 滑动窗口解决的是“连续区间如何增量维护”
  • 哈希解决的是“如何用空间换时间，快速建立索引”
  • 递归解决的是“当前问题和子问题结构一致”
  • 回溯解决的是“需要系统枚举，再及时撤销状态”

如果看问题时能先看出这五类结构，再选写法，算法就开始变成工程能力，而不是题库记忆。

三、先看这篇文章里的小项目

假设现在有一个最小的巡检失败分析器，输入来自两个来源：

  • 主动巡检任务
  • 被动告警回传

每条失败记录至少有这些字段：

1
2
3
4
5
6
7
type FailureEvent struct {
	ID         string
	Service    string
	OccurredAt time.Time
	LatencyMS  int
	Severity   int
}

此外系统还维护一棵服务依赖树：

1
2
3
4
type ServiceNode struct {
	Name     string
	Children []*ServiceNode
}

到了事故分析阶段，工具要完成这条链：

  1. 先用哈希对重复事件做去重和按服务聚合
  2. 再把两份已经排好序的失败服务名合并成一份稳定列表
  3. 再用滑动窗口找出失败最集中的时间段
  4. 再递归展开依赖树，找出受影响服务
  5. 最后在 30 分钟预算内，用回溯选一组补救动作

这不是为了把五个知识点硬塞在一起，而是因为真实工程里的分析链路，往往就是多个模式连续出现。

四、先给一个最小可运行版本

先看一份最小代码骨架，后面每一段都围绕它展开。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
package analyzer

import (
	"errors"
	"sort"
	"time"
)

type FailureEvent struct {
	ID         string
	Service    string
	OccurredAt time.Time
	LatencyMS  int
	Severity   int
}

type ServiceNode struct {
	Name     string
	Children []*ServiceNode
}

type RecoveryAction struct {
	Name      string
	CostMin   int
	Benefit   int
	AppliesTo string
}

func BuildUniqueEvents(events []FailureEvent) []FailureEvent {
	seen := make(map[string]struct{}, len(events))
	result := make([]FailureEvent, 0, len(events))

	for _, event := range events {
		if _, ok := seen[event.ID]; ok {
			continue
		}
		seen[event.ID] = struct{}{}
		result = append(result, event)
	}

	return result
}

func MergeSortedServices(a, b []string) []string {
	i := 0
	j := 0
	result := make([]string, 0, len(a)+len(b))

	appendIfNeeded := func(value string) {
		if len(result) == 0 || result[len(result)-1] != value {
			result = append(result, value)
		}
	}

	for i < len(a) && j < len(b) {
		switch {
		case a[i] == b[j]:
			appendIfNeeded(a[i])
			i++
			j++
		case a[i] < b[j]:
			appendIfNeeded(a[i])
			i++
		default:
			appendIfNeeded(b[j])
			j++
		}
	}

	for i < len(a) {
		appendIfNeeded(a[i])
		i++
	}

	for j < len(b) {
		appendIfNeeded(b[j])
		j++
	}

	return result
}

func FindBusiestWindow(events []FailureEvent, window time.Duration) (int, time.Time, time.Time, error) {
	if len(events) == 0 {
		return 0, time.Time{}, time.Time{}, errors.New("empty events")
	}

	sorted := append([]FailureEvent(nil), events...)
	sort.Slice(sorted, func(i, j int) bool {
		return sorted[i].OccurredAt.Before(sorted[j].OccurredAt)
	})

	left := 0
	bestCount := 0
	bestStart := sorted[0].OccurredAt
	bestEnd := sorted[0].OccurredAt

	for right := 0; right < len(sorted); right++ {
		for sorted[right].OccurredAt.Sub(sorted[left].OccurredAt) > window {
			left++
		}

		currentCount := right - left + 1
		if currentCount > bestCount {
			bestCount = currentCount
			bestStart = sorted[left].OccurredAt
			bestEnd = sorted[right].OccurredAt
		}
	}

	return bestCount, bestStart, bestEnd, nil
}

func WalkDependencies(node *ServiceNode, visit func(*ServiceNode), seen map[string]struct{}) {
	if node == nil {
		return
	}
	if _, ok := seen[node.Name]; ok {
		return
	}

	seen[node.Name] = struct{}{}
	visit(node)

	for _, child := range node.Children {
		WalkDependencies(child, visit, seen)
	}
}

func ChooseRecoveryPlan(actions []RecoveryAction, budget int) (int, []RecoveryAction) {
	bestScore := 0
	bestPlan := make([]RecoveryAction, 0)
	path := make([]RecoveryAction, 0)

	var dfs func(index int, used int, score int)
	dfs = func(index int, used int, score int) {
		if used > budget {
			return
		}
		if score > bestScore {
			bestScore = score
			bestPlan = append([]RecoveryAction(nil), path...)
		}
		if index == len(actions) {
			return
		}

		path = append(path, actions[index])
		dfs(index+1, used+actions[index].CostMin, score+actions[index].Benefit)
		path = path[:len(path)-1]

		dfs(index+1, used, score)
	}

	dfs(0, 0, 0)
	return bestScore, bestPlan
}

这一版还很简化，但已经能看出五种模式各自在负责什么。

五、哈希先解决“去重、索引、聚合”

算法模式里，哈希通常最先在工程里落地，因为它最贴近真实数据处理。

例如同一次事故里，一条失败事件可能从多个来源重复进来：

  • 巡检系统发了一次
  • 告警系统同步了一次
  • 补偿任务重试时又回传了一次

如果不先去重，后面所有统计都会偏大。

最小去重写法通常就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func BuildUniqueEvents(events []FailureEvent) []FailureEvent {
	seen := make(map[string]struct{}, len(events))
	result := make([]FailureEvent, 0, len(events))

	for _, event := range events {
		if _, ok := seen[event.ID]; ok {
			continue
		}
		seen[event.ID] = struct{}{}
		result = append(result, event)
	}

	return result
}

这段代码在做的事很直接：

  • seen 是索引
  • event.ID 是 key
  • struct{} 是最低成本的存在标记

这不是算法题语境里的“哈希表模板”，而是工程里最常见的一种空间换时间。

继续往前走一步，哈希还可以直接承担聚合：

1
2
3
4
5
6
7
func GroupByService(events []FailureEvent) map[string][]FailureEvent {
	result := make(map[string][]FailureEvent)
	for _, event := range events {
		result[event.Service] = append(result[event.Service], event)
	}
	return result
}

于是“按服务聚合失败次数、按事件 ID 去重、按服务名建立快速索引”这三件事，本质上都是同一类思路。

什么时候优先想到哈希

下面这些信号一出现，就可以先想哈希：

  • 要快速判断某个元素是否出现过
  • 要做去重
  • 要把元素按某个 key 分类
  • 要缓存中间结果
  • 要从 O(n^2) 的查找改成接近 O(n)

一个错误例子

下面这种写法在数据量小的时候能跑，但规模一上来就会拖垮：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func BuildUniqueEventsSlow(events []FailureEvent) []FailureEvent {
	result := make([]FailureEvent, 0, len(events))

	for _, event := range events {
		exists := false
		for _, item := range result {
			if item.ID == event.ID {
				exists = true
				break
			}
		}
		if !exists {
			result = append(result, event)
		}
	}

	return result
}

问题不在“这样写一定错”，而在于它会把一次普通去重，写成随着数据量增长快速退化的嵌套扫描。

六、双指针解决“两个序列一起走”

双指针最常见的误解，是把它缩成“数组题技巧”。

实际上它更像一种过程控制方式：
当两个位置都在按某种顺序推进时，双指针可以避免反复回头。

例如有两份已经排好序的失败服务列表：

  • 一份来自主动巡检
  • 一份来自被动告警

需求是：

  1. 合并成一份升序结果
  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
27
28
29
30
31
32
33
34
35
36
37
38
func MergeSortedServices(a, b []string) []string {
	i := 0
	j := 0
	result := make([]string, 0, len(a)+len(b))

	appendIfNeeded := func(value string) {
		if len(result) == 0 || result[len(result)-1] != value {
			result = append(result, value)
		}
	}

	for i < len(a) && j < len(b) {
		switch {
		case a[i] == b[j]:
			appendIfNeeded(a[i])
			i++
			j++
		case a[i] < b[j]:
			appendIfNeeded(a[i])
			i++
		default:
			appendIfNeeded(b[j])
			j++
		}
	}

	for i < len(a) {
		appendIfNeeded(a[i])
		i++
	}

	for j < len(b) {
		appendIfNeeded(b[j])
		j++
	}

	return result
}

双指针在这里的价值，不只是复杂度更低，还有两个更实际的工程好处：

  1. 结果天然稳定
    因为输入有序，所以输出顺序可预测，测试也更稳

  2. 不需要中间大索引
    如果只是合并两份已排序结果，双指针比“先拼起来再排序再去重”更直观

双指针适合哪些工程场景

  • 合并两个已排序日志流
  • 对齐两份时间序列
  • 扫描两个版本的配置差异
  • 同时遍历请求列表和白名单列表
  • 找出两份已排序数据的交集、并集、差集

一个容易漏掉的坑

最常见的问题是尾部元素没处理完。

例如只写：

1
2
3
for i < len(a) && j < len(b) {
	// ...
}

然后就直接返回，剩余的 a[i:] 或 b[j:] 就丢了。

双指针代码看起来简单，但每次写完最好主动检查三件事：

  1. 相等分支是否同时推进两个指针
  2. 单边推进后会不会漏掉尾部
  3. 是否需要去重，去重逻辑放在了哪里

七、滑动窗口解决“连续区间的增量统计”

滑动窗口最适合的，不是“随便一段数据”，而是：

  • 数据有顺序
  • 关注的是连续区间
  • 窗口向前移动时，大量信息可以复用

例如事故分析时，常见问题不是“总共失败多少次”，而是：

10 分钟内失败最密集的窗口出现在哪里？

这类问题如果对每个起点都重新统计一遍，会变得很慢。
如果事件本身按时间有序，滑动窗口就很自然。

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
27
28
29
30
func FindBusiestWindow(events []FailureEvent, window time.Duration) (int, time.Time, time.Time, error) {
	if len(events) == 0 {
		return 0, time.Time{}, time.Time{}, errors.New("empty events")
	}

	sorted := append([]FailureEvent(nil), events...)
	sort.Slice(sorted, func(i, j int) bool {
		return sorted[i].OccurredAt.Before(sorted[j].OccurredAt)
	})

	left := 0
	bestCount := 0
	bestStart := sorted[0].OccurredAt
	bestEnd := sorted[0].OccurredAt

	for right := 0; right < len(sorted); right++ {
		for sorted[right].OccurredAt.Sub(sorted[left].OccurredAt) > window {
			left++
		}

		currentCount := right - left + 1
		if currentCount > bestCount {
			bestCount = currentCount
			bestStart = sorted[left].OccurredAt
			bestEnd = sorted[right].OccurredAt
		}
	}

	return bestCount, bestStart, bestEnd, nil
}

这里的核心不是“两个指针又出现了一次”，而是窗口含义发生了变化：

  • left 和 right 不是在合并两个数组
  • 而是在维护一个始终满足条件的连续区间

工程里哪些地方经常是滑动窗口

  • 某一段时间内的失败次数统计
  • 频控或限流窗口
  • 连续 N 分钟的 CPU、QPS、错误率峰值
  • 实时日志里异常关键字的活跃窗口
  • 测试平台里一批任务的连续超时区间

一个错误例子

下面这种写法很容易把窗口边界搞错：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func FindBusiestWindowWrong(events []FailureEvent, window time.Duration) int {
	left := 0
	best := 0

	for right := 0; right < len(events); right++ {
		if events[right].OccurredAt.Sub(events[left].OccurredAt) > window {
			left++
		}
		if right-left+1 > best {
			best = right - left + 1
		}
	}

	return best
}

问题有两个：

  1. 只 left++ 一次，可能窗口依旧超范围
  2. 假设输入已经有序，但函数本身没有保证

所以这里需要的是 for 收缩窗口，而不是 if。

八、递归解决“结构和子结构长得一样”

递归在工程里最常出现的地方不是数学题，而是层级结构：

  • 目录
  • 树形配置
  • 组织架构
  • 服务依赖图
  • 菜单或权限树

例如现在有一棵服务依赖树：

1
2
3
4
5
6
7
gateway
├── order-api
│   ├── mysql
│   └── redis
└── user-api
    ├── mysql
    └── profile-cache

当 gateway 的请求大面积失败时，排查工具常常要做的一件事是：
递归展开依赖树，找出整条影响链。

最小写法可以是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func WalkDependencies(node *ServiceNode, visit func(*ServiceNode), seen map[string]struct{}) {
	if node == nil {
		return
	}
	if _, ok := seen[node.Name]; ok {
		return
	}

	seen[node.Name] = struct{}{}
	visit(node)

	for _, child := range node.Children {
		WalkDependencies(child, visit, seen)
	}
}

这段代码体现了递归在工程里的真实价值：

  1. 当前节点怎么处理
  2. 子节点重复同一套逻辑
  3. 用 seen 防止环导致死循环

为什么这里不用一开始就写迭代

递归不是永远更好，但在“节点处理逻辑 + 子节点重复处理”这种结构里，它表达最直接。

如果一上来就改成手动栈，代码通常会更长。
等到深度很大、调用栈风险明显、或需要更强的过程控制时，再改迭代会更合适。

一个错误例子

下面这种递归在真实依赖图里很危险：

1
2
3
4
5
6
7
8
9
10
func WalkDependenciesWrong(node *ServiceNode, visit func(*ServiceNode)) {
	if node == nil {
		return
	}

	visit(node)
	for _, child := range node.Children {
		WalkDependenciesWrong(child, visit)
	}
}

如果依赖图里有环：

  • gateway -> order-api
  • order-api -> gateway

这段代码会无限递归。

所以工程里的递归，除了基本终止条件，经常还要再补一层“访问过”保护。

九、回溯解决“在约束下系统枚举选择”

回溯最容易被误读成“暴力搜索”。

更准确一点，它解决的是：

当所有方案都需要被系统尝试，但尝试过程中可以及时剪枝和撤销状态时，回溯是一种很自然的组织方式。

例如事故发生后，现在有一组候选补救动作：

1
2
3
4
5
6
actions := []RecoveryAction{
	{Name: "restart-order-api", CostMin: 8, Benefit: 9, AppliesTo: "order-api"},
	{Name: "flush-profile-cache", CostMin: 4, Benefit: 5, AppliesTo: "profile-cache"},
	{Name: "scale-gateway", CostMin: 10, Benefit: 12, AppliesTo: "gateway"},
	{Name: "switch-readonly-mysql", CostMin: 14, Benefit: 15, AppliesTo: "mysql"},
}

现在值班窗口只剩 20 分钟，希望选一组收益更高的动作。
候选动作数量不大时，回溯就很合适：

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
27
28
func ChooseRecoveryPlan(actions []RecoveryAction, budget int) (int, []RecoveryAction) {
	bestScore := 0
	bestPlan := make([]RecoveryAction, 0)
	path := make([]RecoveryAction, 0)

	var dfs func(index int, used int, score int)
	dfs = func(index int, used int, score int) {
		if used > budget {
			return
		}
		if score > bestScore {
			bestScore = score
			bestPlan = append([]RecoveryAction(nil), path...)
		}
		if index == len(actions) {
			return
		}

		path = append(path, actions[index])
		dfs(index+1, used+actions[index].CostMin, score+actions[index].Benefit)
		path = path[:len(path)-1]

		dfs(index+1, used, score)
	}

	dfs(0, 0, 0)
	return bestScore, bestPlan
}

这里最重要的不是“递归调用了两次”，而是理解回溯的状态管理：

  • path 代表当前方案
  • 选择一个动作时追加到 path
  • 退出这一分支时撤销这个动作
  • 超预算时立即剪枝

工程里哪些场景会用到回溯

  • 预算受限时组合补救动作
  • 测试参数组合枚举
  • 权限路径组合验证
  • 任务批次切分
  • 小规模资源调度

一个很常见的坑

下面这种写法会把后续修改污染到 bestPlan：

1
2
3
4
if score > bestScore {
	bestScore = score
	bestPlan = path
}

因为 path 后面还会继续被 append 和截断。
这里要拷贝当前切片快照，而不是直接复用底层数组。

十、把五种模式串成一条完整处理链

只分别看小函数还不够，工程里的关键是它们如何串起来。

下面给一个简化版流程：

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
27
28
29
30
31
32
33
34
35
func Analyze(
	active []FailureEvent,
	passive []FailureEvent,
	root *ServiceNode,
	actions []RecoveryAction,
) error {
	allEvents := append(append([]FailureEvent(nil), active...), passive...)
	uniqueEvents := BuildUniqueEvents(allEvents)

	activeServices := ExtractSortedServices(active)
	passiveServices := ExtractSortedServices(passive)
	mergedServices := MergeSortedServices(activeServices, passiveServices)

	count, start, end, err := FindBusiestWindow(uniqueEvents, 10*time.Minute)
	if err != nil {
		return err
	}

	affected := make([]string, 0)
	WalkDependencies(root, func(node *ServiceNode) {
		affected = append(affected, node.Name)
	}, map[string]struct{}{})

	bestScore, plan := ChooseRecoveryPlan(actions, 20)

	_ = mergedServices
	_ = count
	_ = start
	_ = end
	_ = affected
	_ = bestScore
	_ = plan

	return nil
}

还缺一个辅助函数：

1
2
3
4
5
6
7
8
func ExtractSortedServices(events []FailureEvent) []string {
	names := make([]string, 0, len(events))
	for _, event := range events {
		names = append(names, event.Service)
	}
	sort.Strings(names)
	return names
}

这条链本身就说明了一个很重要的工程判断：

  • 不是先问“今天写哪个算法”
  • 而是先问“当前数据是去重问题、顺序问题、连续区间问题、层级问题，还是选择问题”

模式只是结果，不是起点。

十一、测试时不要只测结果，要测边界和状态

这些函数虽然不大，但每个都有清晰的边界条件，非常适合表驱动测试。

1. 先测哈希去重

1
2
3
4
5
6
7
8
9
10
11
12
13
func TestBuildUniqueEvents(t *testing.T) {
	now := time.Date(2024, 1, 1, 10, 0, 0, 0, time.UTC)
	events := []FailureEvent{
		{ID: "e1", Service: "order-api", OccurredAt: now},
		{ID: "e1", Service: "order-api", OccurredAt: now},
		{ID: "e2", Service: "user-api", OccurredAt: now},
	}

	got := BuildUniqueEvents(events)
	if len(got) != 2 {
		t.Fatalf("expected 2 unique events, got %d", len(got))
	}
}

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
27
28
29
30
func TestMergeSortedServices(t *testing.T) {
	cases := []struct {
		name string
		a    []string
		b    []string
		want []string
	}{
		{
			name: "deduplicate overlap",
			a:    []string{"gateway", "order-api", "redis"},
			b:    []string{"gateway", "mysql", "redis"},
			want: []string{"gateway", "mysql", "order-api", "redis"},
		},
		{
			name: "one side empty",
			a:    nil,
			b:    []string{"mysql"},
			want: []string{"mysql"},
		},
	}

	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			got := MergeSortedServices(tc.a, tc.b)
			if !reflect.DeepEqual(got, tc.want) {
				t.Fatalf("want %v, got %v", tc.want, got)
			}
		})
	}
}

3. 滑动窗口要重点测边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func TestFindBusiestWindow(t *testing.T) {
	base := time.Date(2024, 1, 1, 10, 0, 0, 0, time.UTC)
	events := []FailureEvent{
		{ID: "e1", OccurredAt: base},
		{ID: "e2", OccurredAt: base.Add(2 * time.Minute)},
		{ID: "e3", OccurredAt: base.Add(4 * time.Minute)},
		{ID: "e4", OccurredAt: base.Add(20 * time.Minute)},
	}

	count, _, _, err := FindBusiestWindow(events, 5*time.Minute)
	if err != nil {
		t.Fatalf("expected nil error, got %v", err)
	}
	if count != 3 {
		t.Fatalf("expected 3, got %d", count)
	}
}

4. 递归要测环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func TestWalkDependenciesWithCycle(t *testing.T) {
	a := &ServiceNode{Name: "gateway"}
	b := &ServiceNode{Name: "order-api"}
	c := &ServiceNode{Name: "mysql"}

	a.Children = []*ServiceNode{b}
	b.Children = []*ServiceNode{c}
	c.Children = []*ServiceNode{a}

	visited := make([]string, 0)
	WalkDependencies(a, func(node *ServiceNode) {
		visited = append(visited, node.Name)
	}, map[string]struct{}{})

	if len(visited) != 3 {
		t.Fatalf("expected 3 visited nodes, got %d", len(visited))
	}
}

5. 回溯要测“最优方案”和“状态污染”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func TestChooseRecoveryPlan(t *testing.T) {
	actions := []RecoveryAction{
		{Name: "restart-order-api", CostMin: 8, Benefit: 9},
		{Name: "flush-cache", CostMin: 4, Benefit: 5},
		{Name: "scale-gateway", CostMin: 10, Benefit: 12},
	}

	score, plan := ChooseRecoveryPlan(actions, 12)
	if score != 14 {
		t.Fatalf("expected score 14, got %d", score)
	}
	if len(plan) != 2 {
		t.Fatalf("expected 2 actions, got %d", len(plan))
	}
}

如果把这几组测试都补齐，后面再重构这些函数时，信心会高很多。

十二、一个真实一点的小项目版本

只讲小函数还不够，下面把它们放进一个更接近项目的最小程序里：
事故摘要生成器。

它输出的结果大概是：

1
2
3
4
5
6
7
8
9
type IncidentSummary struct {
	Services           []string
	BusiestCount       int
	BusiestWindowStart time.Time
	BusiestWindowEnd   time.Time
	AffectedServices   []string
	BestActionScore    int
	BestActions        []string
}

核心实现可以是：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func BuildIncidentSummary(
	active []FailureEvent,
	passive []FailureEvent,
	root *ServiceNode,
	actions []RecoveryAction,
) (IncidentSummary, error) {
	allEvents := BuildUniqueEvents(append(append([]FailureEvent(nil), active...), passive...))

	count, start, end, err := FindBusiestWindow(allEvents, 10*time.Minute)
	if err != nil {
		return IncidentSummary{}, err
	}

	services := MergeSortedServices(
		ExtractSortedServices(active),
		ExtractSortedServices(passive),
	)

	affected := make([]string, 0)
	WalkDependencies(root, func(node *ServiceNode) {
		affected = append(affected, node.Name)
	}, map[string]struct{}{})
	sort.Strings(affected)

	score, plan := ChooseRecoveryPlan(actions, 20)
	actionNames := make([]string, 0, len(plan))
	for _, action := range plan {
		actionNames = append(actionNames, action.Name)
	}

	return IncidentSummary{
		Services:           services,
		BusiestCount:       count,
		BusiestWindowStart: start,
		BusiestWindowEnd:   end,
		AffectedServices:   affected,
		BestActionScore:    score,
		BestActions:        actionNames,
	}, nil
}

这段代码的工程意义，不在于业务本身有多复杂，而在于它说明了：

  • 算法模式完全可以拆成一组可测试的小函数
  • 每个函数只承担一个明确职责
  • 小函数组合起来，最后形成一条完整分析链

这才是“题型能力走进工程”的关键一步。

十三、几类最常见的错误写法

把模式记住不难，真正容易出错的是实现细节和边界。

1. 哈希 key 选错

如果把 Service 当成唯一 key 去重：

1
seen[event.Service] = struct{}{}

那同一服务在不同时间的失败事件会被错误合并。
所以先问“唯一性定义是什么”，再决定 key。

2. 双指针输入未排序

如果 a 和 b 本身没排序，双指针的前提就不存在了。
这时要么先排序，要么换别的策略。

3. 滑动窗口边界条件不清楚

窗口是：

  • <= 10 分钟
  • 还是 < 10 分钟

这个判断会直接影响边界事件是否落进窗口。
代码里最好明确写出来，测试里也补一条卡边界的 case。

4. 递归没有环保护

树可以不防环，图通常要防。
一旦输入来源是注册中心、依赖配置、服务发现结果，保守做法是默认它可能形成环。

5. 回溯没有撤销状态

漏掉这一句：

1
path = path[:len(path)-1]

后面的路径就会被污染。

6. 回溯最优结果没有拷贝快照

漏掉切片拷贝时，bestPlan 看起来更新了，最后却可能和预期完全不同。

十四、排障时怎么快速判断问题出在哪一层

如果这类代码上线后结果不对，可以按下面顺序排：

1. 先看输入前提有没有被满足

  • 双指针输入是否有序
  • 滑动窗口输入是否按时间可比较
  • 递归输入是否可能形成环
  • 回溯预算是否允许负值或零值动作

很多问题不是算法实现坏了，而是调用方没满足前提。

2. 再看边界值

  • 空切片怎么办
  • 单元素怎么办
  • 时间窗口刚好压线怎么办
  • 预算刚好等于动作成本怎么办
  • 依赖树根节点为空怎么办

如果边界 case 没补测试，线上结果很容易在这些地方偏掉。

3. 最后看状态是否被意外共享

Go 里切片、map、闭包变量共享状态时，最容易把这类小函数写出隐藏 bug。

例如：

  • 回溯里的 path 没有正确撤销
  • 递归遍历时复用同一个结果切片但没隔离
  • 返回内部 map 给外层后又被修改

这类问题通常表现为：

  • 单测偶尔过
  • 输出顺序时好时坏
  • 数据条数看起来不稳定

十五、这些模式的使用边界

算法模式有价值，但也有明显边界。

1. 双指针的前提是“序”

如果输入完全无序，还硬上双指针，代码只会更绕。

2. 滑动窗口更适合连续区间

如果问题不是连续区间，而是任意子集选择，滑动窗口通常就不合适。

3. 哈希会换来额外内存成本

数据量非常大时，需要再评估：

  • 内存是否扛得住
  • key 是否过长
  • 是否需要分桶、落盘或流式处理

4. 递归受调用栈深度限制

树特别深、输入又不可控时，要考虑改成显式栈迭代。

5. 回溯更适合小规模枚举

候选动作数量变大后，回溯会迅速膨胀。
这时要考虑：

  • 剪枝
  • 排序优化
  • 动态规划
  • 贪心近似

回溯不是不能用，而是要知道它适合解决的规模区间。

十六、练习题

如果想把这一篇真正吃透，可以自己补这几道练习：

  1. 把 BuildUniqueEvents 改成“按 Service + Minute 去重”，看 key 设计怎么变化
  2. 给 MergeSortedServices 增加一个 exclude 列表，输出时过滤黑名单服务
  3. 把 FindBusiestWindow 改成同时返回窗口里的服务名集合
  4. 给 WalkDependencies 增加错误返回，让 visit 失败时能中断遍历
  5. 给 ChooseRecoveryPlan 增加一个约束：同一服务只能选一个动作
  6. 思考当候选动作从 10 个涨到 200 个时，为什么单纯回溯已经不再合适

这几题做完，模式和工程场景之间的连接会更牢。

十七、最后总结

双指针、滑动窗口、哈希、递归、回溯，在工程里真正重要的不是名字，而是它们各自对应的数据形状和问题结构：

  • 数据要去重、聚合、快速索引，先想哈希
  • 两个有序序列一起推进，先想双指针
  • 连续区间统计需要增量维护，先想滑动窗口
  • 当前结构和子结构重复出现，先想递归
  • 在约束下系统枚举选择，先想回溯

如果只把它们当题型，做完题就断了。
如果把它们看成几类稳定的思考模式，后面写 Go 服务、测试工具、分析脚本、任务编排时，会越来越自然地用出来。

下一篇如果继续往后接，更自然的方向通常有两个：

  • 一个是继续讲动态规划，说明它和回溯的关系
  • 另一个是把这些模式放进更完整的服务设计和性能权衡里

到这里，算法就不再只是“刷题阶段的附属品”，而开始变成可复用的工程判断。