常用枚举技巧:基础(一)

发布于:2025-06-11 ⋅ 阅读:(41) ⋅ 点赞:(0)

常用枚举技巧:基础(一)

在这里插入图片描述

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

LeetCode 1. 两数之和

思路

这道题目非常的经典,但是今天重做之前我发现我过去都是通过两次循环,以 O ( 2 n ) O(2n) 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 := -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
}

网站公告

今日签到

点亮在社区的每一天
去签到