Easy

题目描述

给定一个整数数组 nums 和一个整数 k。

返回数组中所有频率能被 k 整除的元素的和，如果没有这样的元素则返回 0。

注意：如果一个元素的总频率能被 k 整除，则该元素在和中恰好包含其在数组中出现的次数。

示例 1：

输入：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。

示例 2：

输入：nums = [1,2,3,4,5], k = 2
输出：0
解释：
没有元素出现偶数次，所以总和为 0。

示例 3：

输入：nums = [4,4,4,1,2,3], k = 3
输出：12
解释：
- 数字 1 出现 1 次
- 数字 2 出现 1 次
- 数字 3 出现 1 次
- 数字 4 出现 3 次

因此，总和为 4 + 4 + 4 = 12。

约束条件：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

解题思路

这是一个简单的哈希表计数问题。解题思路如下：

核心思路：

  1. 统计每个元素在数组中的出现频率
  2. 检查每个元素的频率是否能被 k 整除
  3. 如果能整除，则将该元素的所有出现次数都加入结果

具体步骤：

  1. 使用哈希表记录每个数字的出现次数
  2. 遍历哈希表，对于每个数字，检查其频率是否能被 k 整除
  3. 如果能整除，将 数字值 × 出现次数 加入总和
  4. 返回最终的总和

时间复杂度分析：

  • 第一次遍历数组统计频率：O(n)
  • 遍历哈希表计算结果：O(m)，其中 m 是不同元素的个数
  • 总体时间复杂度：O(n)

这是一个直接按题意模拟的问题，实现简单明了。

代码实现

class Solution {
public:
    int sumDivisibleByK(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        
        // 统计每个元素的频率
        for (int num : nums) {
            freq[num]++;
        }
        
        int result = 0;
        // 检查频率是否能被k整除
        for (auto& pair : freq) {
            int num = pair.first;
            int count = pair.second;
            if (count % k == 0) {
                result += num * count;
            }
        }
        
        return result;
    }
};

class Solution:
    def sumDivisibleByK(self, nums: List[int], k: int) -> int:
        from collections import Counter
        
        # 统计每个元素的频率
        freq = Counter(nums)
        
        result = 0
        # 检查频率是否能被k整除
        for num, count in freq.items():
            if count % k == 0:
                result += num * count
        
        return result

public class Solution {
    public int SumDivisibleByK(int[] nums, int k) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        // 统计每个元素的频率
        foreach (int num in nums) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }
        
        int result = 0;
        // 检查频率是否能被k整除
        foreach (var pair in freq) {
            int num = pair.Key;
            int count = pair.Value;
            if (count % k == 0) {
                result += num * count;
            }
        }
        
        return result;
    }
}

var sumDivisibleByK = function(nums, k) {
    const freq = {};
    
    for (const num of nums) {
        freq[num] = (freq[num] || 0) + 1;
    }
    
    let sum = 0;
    for (const num in freq) {
        if (freq[num] % k === 0) {
            sum += num * freq[num];
        }
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表计数O(n)O(m)

其中 n 是数组长度，m 是不同元素的个数（最坏情况下 m = n）。