Hot100（Go）：哈希三题

记录一下 LeetCode Hot100 里三道哈希题的思路和 Go 实现。原截图保留作学习记录，下面的分组测试已经补上顺序归一化；独立输入输出版本见 ACM 写法。

哈希

1. 两数之和

遍历到当前数字时，先在 map 中找它的另一半 target-num，找到就返回。当前数字要在查找之后再加入 map，避免使用同一个下标两次。比如 [3, 3]，第二个 3 可以找到前面的 3，结果是 [0, 1]。

按 map 平均 O(1) 查找计算，时间 O(n)，额外空间 O(n)。原题保证有一个答案；下面找不到时返回 nil。

题解

package main

import (
	"fmt"
	"reflect"
)

func twoSum(nums []int, target int) (ans []int) {
	mp := map[int]int{}

	for idx, num := range nums {
		if i, ok := mp[target-num]; ok {
			return []int{i, idx}
		}
		mp[num] = idx
	}

	return ans
}

func main() {
	testCases := []struct {
		nums   []int
		target int
		ans    []int
	}{
		{nums: []int{2, 7, 11, 15}, target: 9, ans: []int{0, 1}},
		{nums: []int{3, 2, 4}, target: 6, ans: []int{1, 2}},
		{nums: []int{3, 3}, target: 6, ans: []int{0, 1}},
	}

	for _, t := range testCases {
		fmt.Println(reflect.DeepEqual(twoSum(t.nums, t.target), t.ans))
	}
}

49. 字母异位词分组

把每个单词的字节排序，相同字母组成的单词就会得到同一个键，再按键分组。这里沿用原题的小写英文字母范围，所以用 byte 排序即可；不能直接把这套处理当成任意 Unicode 单词的规则。

单词最长为 L，分组平均时间 O(nL log L)，额外空间用于保存分组结果。Go 的 map 遍历顺序没有保证，题目又允许任意组顺序，所以测试前要分别排序每组和外层分组，再比较；直接 DeepEqual 可能把正确结果判成 false。

题解

package main

import (
	"fmt"
	"reflect"
	"slices"
)

func groupAnagrams(strs []string) [][]string {
	mp := map[string][]string{}

	for _, str := range strs {
		s := []byte(str)
		slices.Sort(s)
		mp[string(s)] = append(mp[string(s)], str)
	}

	ans := make([][]string, 0, len(mp))

	for i := range mp {
		ans = append(ans, mp[i])
	}

	return ans
}

func main() {
	testCases := []struct {
		strs []string
		ans  [][]string
	}{
		{
			[]string{"eat", "tea", "tan", "ate", "nat", "bat"},
			[][]string{
				{"eat", "tea", "ate"},
				{"tan", "nat"},
				{"bat"},
			},
		},
		{
			[]string{""},
			[][]string{
				{""},
			},
		},
		{
			[]string{"a"},
			[][]string{
				{"a"},
			},
		},
	}

	for _, t := range testCases {
		got := groupAnagrams(t.strs)
		for _, group := range got {
			slices.Sort(group)
		}
		for _, group := range t.ans {
			slices.Sort(group)
		}
		less := func(a, b []string) int { return slices.Compare(a, b) }
		slices.SortFunc(got, less)
		slices.SortFunc(t.ans, less)
		fmt.Println(reflect.DeepEqual(got, t.ans))
	}
}

128. 最长连续序列

先用集合去掉重复元素。只有 x-1 不存在时，才把 x 当成连续段起点向后数。否则每个数字都重新扫描一段，容易变成重复工作。

每段只从起点展开，平均时间 O(n)，额外空间 O(n)。空数组返回 0；重复元素不能增加长度，负数同样可以形成连续段。

题解

package main

import "fmt"

func longestConsecutive(nums []int) int {
	ans := 0
	mp := map[int]bool{}

	for _, num := range nums {
		mp[num] = true
	}

	for i := range mp {
		if mp[i-1] == true {
			continue
		}
		cnt := 1

		for mp[i+1] == true {
			i += 1
			cnt += 1
		}

		ans = max(ans, cnt)
	}

	return ans
}

func main() {
	testCases := []struct {
		nums []int
		ans  int
	}{
		{[]int{100, 4, 200, 1, 3, 2}, 4},
		{[]int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}, 9},
		{[]int{1, 0, 1, 2}, 3},
	}

	for _, t := range testCases {
		fmt.Println(longestConsecutive(t.nums) == t.ans)
	}
}

参考资料

原题与输入范围：两数之和、异位词分组、最长连续序列。map 遍历规则见 Go 语言规范。