2026-03-10：缺失的最小倍数。用go语言，给定一个整数数组 nums 和一个整数 k，找出最小的正整数 m，满足两点：m 是 k 的倍数（即可表示

福大大架构师每日一题

发布于 2026-03-31 20:53:31

860

2026-03-10：缺失的最小倍数。用go语言，给定一个整数数组 nums 和一个整数 k，找出最小的正整数 m，满足两点：m 是 k 的倍数（即可表示为 k·t，t 为正整数），且 m 不出现在 nums 中。换言之，求最小的正整数 t（t ≥ 1），使得 k·t 不属于 nums。

1 <= nums.length <= 100。

1 <= nums[i] <= 100。

1 <= k <= 100。

输入： nums = [8,2,3,4,6], k = 2。

输出： 10。

解释：

当 k = 2 时，其倍数为 2、4、6、8、10、12……，其中在 nums 中缺失的最小倍数是 10。

题目来自力扣3718。

一、代码执行的详细过程

我们以输入 nums = [8,2,3,4,6]、k = 2 为例，分阶段拆解执行逻辑：

阶段1：初始化哈希表（map）并存储数组元素

1. 函数 missingMultiple 接收参数 nums = [8,2,3,4,6] 和 k = 2 后，首先创建一个空的布尔型哈希表 has（键是整数，值表示该整数是否存在于 nums 中）。
2. 遍历数组 nums 中的每一个元素，将元素作为键存入哈希表，值设为 true（表示该数存在）：
- • 遍历到 8：has[8] = true
- • 遍历到 2：has[2] = true
- • 遍历到 3：has[3] = true
- • 遍历到 4：has[4] = true
- • 遍历到 6：has[6] = true 最终哈希表 has 中存储的键值对为：8:true, 2:true, 3:true, 4:true, 6:true。

阶段2：查找缺失的最小 k 倍数

1. 进入无限循环，初始值 x = k = 2，循环逻辑是每次将 x 增加 k（即找下一个 k 的倍数），直到找到不在哈希表中的 x。
2. 第一次循环：x = 2，检查 has[2] → 值为 true（说明 2 在 nums 中），因此 x += 2 → x = 4。
3. 第二次循环：x = 4，检查 has[4] → 值为 true（4 在 nums 中），x += 2 → x = 6。
4. 第三次循环：x = 6，检查 has[6] → 值为 true（6 在 nums 中），x += 2 → x = 8。
5. 第四次循环：x = 8，检查 has[8] → 值为 true（8 在 nums 中），x += 2 → x = 10。
6. 第五次循环：x = 10，检查 has[10] → 哈希表中无此键，值为 false（10 不在 nums 中），满足条件，返回 x = 10。

阶段3：主函数执行

1. main 函数中定义 nums = [8,2,3,4,6]、k = 2，调用 missingMultiple 函数得到返回值 10。
2. 执行 fmt.Println(result)，输出结果 10。

二、时间复杂度与空间复杂度分析

1. 时间复杂度

• 第一步（构建哈希表）：遍历数组 nums，数组长度为 n（本题中 n = 5），这一步的时间复杂度是 O(n)。
• 第二步（查找缺失倍数）：最坏情况下需要遍历 m 个 k 的倍数（m 是找到缺失值前的 k 倍数个数），由于题目中 nums[i] 最大为 100，因此 m 最多不超过 100/k + 1（是一个常数），这一步的时间复杂度可视为 O(1)（常数时间）。
• 总时间复杂度：O(n)（因为常数时间可忽略，核心复杂度由数组遍历决定）。

2. 额外空间复杂度

• 额外空间主要消耗在哈希表 has 上，哈希表存储的键数量等于数组 nums 中不同元素的个数（本题中数组无重复元素，数量为 n = 5）。
• 因此额外空间复杂度为 O(n)（n 为数组长度）。

总结

1. 代码核心逻辑：先通过哈希表快速判断元素是否存在，再从 k 的 1 倍开始依次检查，找到第一个不在哈希表中的 k 倍数。
2. 执行过程关键：哈希表的“存在性查询”是 O(1) 时间，因此能高效找到缺失的最小倍数。
3. 复杂度关键点：时间复杂度为 O(n)（n 为数组长度），额外空间复杂度为 O(n)（哈希表存储数组元素）。

Go完整代码如下：

package main

import (
    "fmt"
)

func missingMultiple(nums []int, k int)int {
    has := map[int]bool{}
    for _, x := range nums {
        has[x] = true
    }
    for x := k; ; x += k {
        if !has[x] {
            return x
        }
    }
}

func main() {
    nums := []int{8, 2, 3, 4, 6}
    k := 2
    result := missingMultiple(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def missingMultiple(nums: List[int], k: int) -> int:
    has = set()
    for x in nums:
        has.add(x)
    
    x = k
    while True:
        if x not in has:
            return x
        x += k

def main():
    nums = [8, 2, 3, 4, 6]
    k = 2
    result = missingMultiple(nums, k)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int missingMultiple(vector<int>& nums, int k) {
    unordered_set<int> has;
    for (int x : nums) {
        has.insert(x);
    }

    for (int x = k; ; x += k) {
        if (has.find(x) == has.end()) {
            return x;
        }
    }
}

int main() {
    vector<int> nums = {8, 2, 3, 4, 6};
    int k = 2;
    int result = missingMultiple(nums, k);
    cout << result << endl;

    return0;
}