LeetCode 一般已经给好函数签名，我们只要写算法。换成 ACM 写法，就得自己读输入、调用函数、输出答案。算法没变，容易出问题的是这些外面的东西。
这里先把哈希三题改成可以独立运行的程序：两数之和、字母异位词分组、最长连续序列，本篇覆盖这三题。
下面的输入输出格式为本地练习自行约定；LeetCode 仍按函数式判题。每段代码单独保存为 main.go，用 go run main.go 运行。
1、两数之和
原题：Two Sum。
思路：遍历到 x 的时候，先查 target-x 是否已经出现。找到就返回这两个位置；没找到再保存当前元素。先查再存，才能避免重复使用同一个位置。
这里的 map 查找按平均 O(1) 计算，整个算法平均 O(n)，额外空间 O(n)。
输入约定：第一行是元素数量 n 和目标值，后面读 n 个整数。输出从 0 开始的两个下标。原题保证有解；这里为了本地测试，把无解情况输出成 -1 -1。
4 9
2 7 11 15输出：
0 1package main
import (
"bufio"
"fmt"
"os"
)
func twoSum(nums []int, target int) (int, int) {
seen := make(map[int]int, len(nums))
for i, x := range nums {
if j, ok := seen[target-x]; ok {
return j, i
}
seen[x] = i
}
return -1, -1
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, target int
if _, err := fmt.Fscan(in, &n, &target); err != nil || n < 0 {
return
}
nums := make([]int, n)
for i := range nums {
if _, err := fmt.Fscan(in, &nums[i]); err != nil {
return
}
}
i, j := twoSum(nums, target)
fmt.Fprintln(out, i, j)
}拿 3 3、两个 0、负数和无解情况再测一下，可以检查是不是错误地用了一次元素两遍。
2、字母异位词分组
原题：Group Anagrams。
字母异位词的字母和数量相同，只是顺序不同。按原题的小写英文字母范围，可以用 [26]int 记录每个字母出现的次数。数组可以做 Go map 的键，这样就不需要给每个单词排序了。
分组平均时间是 O(nL)，L 是单词最大长度。下面为了让本地输出稳定，会给每组和所有组排序；这部分会额外增加排序开销，不能把整个带格式化输出的程序也说成只有 O(nL)。
输入约定：第一行是单词数量，之后每个单词占一行。空行表示空字符串，所以这里用 Scanner 逐行读，不能只用 Fscan 读单词。
6
eat
tea
tan
ate
nat
bat输出为 JSON，方便保留空字符串和分组边界：
[["ate","eat","tea"],["bat"],["nat","tan"]]package main
import (
"bufio"
"encoding/json"
"fmt"
"os"
"sort"
"strconv"
"strings"
)
func groupAnagrams(words []string) [][]string {
groups := make(map[[26]int][]string)
for _, word := range words {
var key [26]int
for _, ch := range word {
key[ch-'a']++
}
groups[key] = append(groups[key], word)
}
result := make([][]string, 0, len(groups))
for _, group := range groups {
sort.Strings(group)
result = append(result, group)
}
sort.Slice(result, func(i, j int) bool {
return result[i][0] < result[j][0]
})
return result
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
if !scanner.Scan() {
return
}
n, err := strconv.Atoi(strings.TrimSpace(scanner.Text()))
if err != nil || n < 0 {
return
}
words := make([]string, n)
for i := range words {
if !scanner.Scan() {
return
}
words[i] = scanner.Text()
for _, ch := range words[i] {
if ch < 'a' || ch > 'z' {
fmt.Fprintln(os.Stderr, "仅支持小写英文字母和空字符串")
return
}
}
}
if err := json.NewEncoder(os.Stdout).Encode(groupAnagrams(words)); err != nil {
fmt.Fprintln(os.Stderr, err)
}
}输入 1 后再给一行空行，结果应为 [[""]]。只剩一个普通单词时也要能正确输出。这两种情况很容易在读输入时被漏掉。
3、最长连续序列
原题：Longest Consecutive Sequence。
先把数字放到集合里。如果 x-1 存在，说明 x 不是一段连续序列的起点，跳过它。只有起点才继续向后数。
这样每个数字不会反复作为起点扫描。按哈希集合平均 O(1) 的查找计算，平均时间 O(n)，额外空间 O(n)。数值范围沿用原题的 [-10^9, 10^9]，不是任意超出 int 边界的整数。
输入约定：先读元素数量，再读对应的整数。数组为空时输出 0。
6
100 4 200 1 3 2输出：
4package main
import (
"bufio"
"fmt"
"os"
)
func longestConsecutive(nums []int) int {
set := make(map[int]bool, len(nums))
for _, x := range nums {
set[x] = true
}
best := 0
for x := range set {
if set[x-1] {
continue
}
length := 1
for next := x + 1; set[next]; next++ {
length++
}
if length > best {
best = length
}
}
return best
}
func main() {
in := bufio.NewReader(os.Stdin)
var n int
if _, err := fmt.Fscan(in, &n); err != nil || n < 0 {
return
}
nums := make([]int, n)
for i := range nums {
if _, err := fmt.Fscan(in, &nums[i]); err != nil {
return
}
}
fmt.Println(longestConsecutive(nums))
}重复数字不会增加序列长度；输入 [1, 0, 1, 2] 的长度还是 3。还可以测空数组、全是同一个数和包含负数的连续段。
4、ACM 写法主要多考虑什么？
算法写完以后，单独检查输入输出：读的是 token 还是整行，题目有没有多组数据，能否出现空字符串，下标从 0 还是 1 开始，输出是否要求固定顺序。
bufio.Reader 配合 fmt.Fscan 比较容易写；如果数据量非常大，再根据评测情况换更快的整数读取器。bufio.Scanner 默认有 token 长度限制，读长文本时需要设置 Buffer，不能把当前的短单词示例直接套到任意大文件。
接口说明：fmt.Fscan、bufio.Scanner。