常用枚举技巧：基础（一）-EW帮帮网

文章目录

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

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

在这里插入图片描述

今天学习序列当中的常见问题。一个最典型的场景就是“双变量问题”，以经典的「LeetCode 1. 两数之和」为例，解决这道题需要维护i, j两个变量，但是在序列中可以通过「枚举右，维护左」的思路来将双变量问题转化为单变量问题，从而只使用一次循环来解决双变量问题（如果直接使用暴力枚举，双变量问题的时间复杂度就是 $O(n^2)$ 。

LeetCode 1. 两数之和

思路

这道题目非常的经典，但是今天重做之前我发现我过去都是通过两次循环，以 $O (2 n)$ 的时间复杂度来解决这个问题的，也就是先用一次循环在 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 := -1
    for 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 := 0
    for _, 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 := 0
    for _, 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 := 0
    for _, dom := range dominoes {
        x, y := dom[0], dom[1]
        if x < y {
            x, y = y, x
        }
        curr := x * 10 + y
        ans += mp[curr]
        mp[curr] ++
    }
    return ans
}

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

文章目录