2026-03-06：出现次数能被 K 整除的元素总和。用go语言，给定一个整数数组 nums 和整数 k，求出数组中那些出现次数能被 k 整除的元素所贡

福大大架构师每日一题

发布于 2026-03-09 13:01:55

660

2026-03-06：出现次数能被 K 整除的元素总和。用go语言，给定一个整数数组 nums 和整数 k，求出数组中那些出现次数能被 k 整除的元素所贡献的总和。具体做法是先统计每个不同元素在数组中出现的次数；若某个元素的出现次数 c 满足 c % k == 0，则把该元素的值按其出现次数累加进结果（即加上 value * c）。如果没有任何元素满足该条件，则返回 0。

1 <= nums.length <= 100。

1 <= nums[i] <= 100。

1 <= k <= 100。

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

输出： 16。

解释：

数字 1 出现 1 次（奇数次）。

数字 2 出现 2 次（偶数次）。

数字 3 出现 4 次（偶数次）。

数字 4 出现 1 次（奇数次）。

因此总和为 2 + 2 + 3 + 3 + 3 + 3 = 16。

题目来自力扣3712。

一、需求理解

你希望我基于提供的Go语言代码，详细拆解“出现次数能被 K 整除的元素总和”问题的解决过程，并分析其时间复杂度和空间复杂度。核心目标是：统计数组中每个元素的出现次数，仅将出现次数能被k整除的元素按其出现次数累加，最终返回这个总和。

二、解题过程分步解析

整个算法的逻辑非常直观，核心是“统计频次 → 筛选条件 → 累加计算”，具体步骤如下：

步骤1：初始化频次统计容器

首先创建一个空的哈希映射（字典）cnt，键是数组中的元素值，值是该元素在数组中出现的次数。这个容器的作用是高效统计每个不同元素的出现次数，避免重复遍历数组。

步骤2：遍历数组，统计每个元素的出现次数

逐个遍历输入数组nums中的每一个元素x：

• 对于当前元素x，检查它是否已经在哈希映射cnt中：
- • 如果存在：将cnt[x]的值加1（表示该元素又出现了一次）；
- • 如果不存在：在cnt中新增键值对x: 1（表示该元素首次出现）。
• 以输入用例nums = [1,2,2,3,3,3,3,4]为例：
- • 遍历到1：cnt[1] = 1；
- • 遍历到第一个2：cnt[2] = 1，遍历到第二个2：cnt[2] = 2；
- • 遍历到4个3：cnt[3]从1逐步增加到4；
- • 遍历到4：cnt[4] = 1；
- • 最终cnt的内容为：{1:1, 2:2, 3:4, 4:1}。

步骤3：遍历频次映射，筛选并累加符合条件的元素总和

初始化结果变量ans为0，然后遍历哈希映射cnt中的每一个键值对（键为元素值x，值为出现次数c）：

• 检查当前元素的出现次数c是否满足c % k == 0（即能被k整除）：
- • 如果满足：将x * c加到ans中（比如元素2出现2次，k=2，2%2=0，所以加22=4；元素3出现4次，4%2=0，所以加34=12）；
- • 如果不满足：跳过该元素（比如元素1出现1次，1%2≠0；元素4出现1次，1%2≠0，均跳过）。
• 以输入用例为例：
- • 处理1: c=1，1%2≠0 → 跳过；
- • 处理2: c=2，2%2=0 → ans += 2*2 → ans=4；
- • 处理3: c=4，4%2=0 → ans += 3*4 → ans=16；
- • 处理4: c=1，1%2≠0 → 跳过；
- • 最终ans的值为16，符合题目输出要求。

步骤4：返回最终结果

遍历完所有键值对后，返回ans作为最终结果。如果没有任何元素满足条件（比如所有元素出现次数都不能被k整除），则ans保持初始值0，符合题目要求。

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

1. 时间复杂度

• 步骤2（统计频次）：遍历数组nums的所有元素，数组长度为n，因此时间复杂度为O(n)；
• 步骤3（筛选累加）：遍历哈希映射cnt的所有键值对，cnt的键的数量最多为n（当数组中所有元素都不同时），因此时间复杂度为O(n)；
• 其他步骤（初始化、返回结果）：时间复杂度为O(1)；
• 总时间复杂度：O(n)（n为数组nums的长度），因为O(n) + O(n) = O(n)。

2. 额外空间复杂度

• 哈希映射cnt：用于存储元素的出现次数，空间占用取决于数组中不同元素的数量，最坏情况下（所有元素都不同）占用O(n)的空间；
• 其他变量（如ans、循环变量x/c等）：占用O(1)的固定空间；
• 总额外空间复杂度：O(n)（最坏情况），最优情况（数组中所有元素都相同）为O(1)。

总结

1. 核心流程：先通过哈希映射统计每个元素的出现次数，再遍历映射筛选出次数能被k整除的元素，按“元素值×出现次数”累加得到总和；
2. 关键操作：哈希映射的频次统计是核心，保证了高效的频次查询和更新；
3. 复杂度：时间复杂度为O(n)（n为数组长度），额外空间复杂度最坏为O(n)、最优为O(1)。

Go完整代码如下：

package main

import (
    "fmt"
)

func sumDivisibleByK(nums []int, k int) (ans int) {
    cnt := map[int]int{}
    for _, x := range nums {
        cnt[x]++
    }

    for x, c := range cnt {
        if c%k == 0 {
            ans += x * c
        }
    }
    return
}

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

Python完整代码如下：

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

def sum_divisible_by_k(nums, k):
    """
    计算数组中出现次数能被k整除的元素与其出现次数的乘积之和
    
    Args:
        nums: 整数数组
        k: 除数
    
    Returns:
        符合条件的元素值乘以出现次数的总和
    """
    # 统计每个数字出现的次数
    cnt = {}
    for x in nums:
        cnt[x] = cnt.get(x, 0) + 1
    
    ans = 0
    # 遍历统计结果
    for x, c in cnt.items():
        if c % k == 0:  # 如果出现次数能被k整除
            ans += x * c
    
    return ans


def main():
    nums = [1, 2, 2, 3, 3, 3, 3, 4]
    k = 2
    result = sum_divisible_by_k(nums, k)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/**
 * 计算数组中出现次数能被k整除的元素与其出现次数的乘积之和
 *
 * @param nums 整数数组
 * @param k 除数
 * @return 符合条件的元素值乘以出现次数的总和
 */
int sumDivisibleByK(const vector<int>& nums, int k) {
    // 统计每个数字出现的次数
    unordered_map<int, int> cnt;
    for (int x : nums) {
        cnt[x]++;
    }

    int ans = 0;
    // 遍历统计结果
    for (const auto& pair : cnt) {
        int x = pair.first;
        int c = pair.second;
        if (c % k == 0) {  // 如果出现次数能被k整除
            ans += x * c;
        }
    }

    return ans;
}

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

    return0;
}