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 語言規範。