常用枚舉技巧：基礎（一）

今天學習序列當中的常見問題。一個最典型的場景就是“雙變量問題”，以經典的「LeetCode 1. 兩數之和」為例，解決這道題需要維護i, j兩個變量，但是在序列中可以通過「枚舉右，維護左」的思路來將雙變量問題轉化為單變量問題，從而只使用一次循環來解決雙變量問題（如果直接使用暴力枚舉，雙變量問題的時間復雜度就是$O(n^2)$。

LeetCode 1. 兩數之和

思路

這道題目非常的經典，但是今天重做之前我發現我過去都是通過兩次循環，以$O(2n)$的時間復雜度來解決這個問題的，也就是先用一次循環在 hash map 中記錄每一個數據出現的位置，然后在第二次循環中枚舉target - nums[i]是否在 hash map 中存在，以及mp[target - nums[i]]是否與當前枚舉的下標j相等。

通過枚舉右維護左，可以通過一次循環直接解決這道問題，也就是將上述兩個循環合并。

Golang 代碼

func twoSum(nums []int, target int) []int {n := len(nums)mp := map[int]int{}for i := 0; i < n; i ++ {if j, ok := mp[target - nums[i]]; ok && i != j {return []int{i, j}}mp[nums[i]] = i}return []int{}
}

LeetCode 2441. 與對應負數同時存在的最大正整數

思路

同樣使用枚舉右維護左的思路，如果枚舉到右側的某個nums[j]，發現-nums[j]已經存在于 hash map 當中，那么就記錄一次答案。

Golang 代碼

func findMaxK(nums []int) int {n := len(nums)mp := map[int]bool{}ans := -1for i := 0; i < n; i ++ {if _, ok := mp[-nums[i]]; ok {curr := nums[i]if curr < 0 {curr = -curr}ans = max(curr, ans)}mp[nums[i]] = true}return ans
}

LeetCode 1512. 好數對的數目

思路

仍然“枚舉右維護左”，我們需要使用 hash map 記錄nums[i]的出現次數，并每次都統計答案。運用 Golang map 的性質，未出現在 map 當中的 key，其 value 為零值，據此我們不需要特判，可以直接維護答案。

Golang 代碼

func numIdenticalPairs(nums []int) int {mp := map[int]int{}ans := 0for _, x := range nums {ans += mp[x]mp[x] ++}return ans
}

LeetCode 2001. 可互換矩形的對數

思路

這道題不要想的過于復雜，直接使用一個 key 為 float64 的 map 記錄答案即可。雖然說對于 Golang 的 map 而言，key 需要是可比較的，而對于 float32/float64 而言，其==比較是不準確的，但是直接使用 float64 的 map AC 這道題是沒問題的。

Golang 代碼

func interchangeableRectangles(rectangles [][]int) int64 {mp := map[float64]int{}ans := 0for _, rec := range rectangles {w, h := rec[0], rec[1]key := float64(w) / float64(h)ans += mp[key]mp[key] ++}return int64(ans)
}

LeetCode 1128. 等價多米諾骨牌對的數量

思路

由于一開始沒有看到「提示」，這道題卡了我一下。看到提示之后發現dominoes[i][j]的值必然是個位數，這就意味著可以將每一個二維數組轉為一個整型，然后使用這個整型值作為 hash map 的 key。之后使用「枚舉右維護左」正常求解答案即可。

Golang 代碼

func numEquivDominoPairs(dominoes [][]int) int {mp := map[int]int{}ans := 0for _, dom := range dominoes {x, y := dom[0], dom[1]if x < y {x, y = y, x}curr := x * 10 + yans += mp[curr]mp[curr] ++}return ans
}