常用枚举技巧：基础（一）

常用枚举技巧：基础（一）

今天学习序列当中的常见问题。一个最典型的场景就是“双变量问题”，以经典的「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
}