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。