Medium
题目描述
给定一个整数数组 nums，返回数组中恰好有四个因数的整数的因数之和。如果数组中没有这样的整数，则返回 0。
示例 1：
输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案是 21 的因数之和。
示例 2：
输入：nums = [21,21]
输出：64
示例 3：
输入：nums = [1,2,3,4,5]
输出：0
约束条件：
1 <= nums.length <= 10^41 <= nums[i] <= 10^5
提示：
- 找出数组中每个元素的因数。
- 你只需要循环到一个数的平方根来找到它的因数。
解题思路
解题思路
这道题要求找到数组中恰好有四个因数的数，并返回这些数的所有因数之和。
首先分析什么数恰好有四个因数：
- 质数的立方：如果 p 是质数，那么 p³ 的因数是 1, p, p², p³，共4个
- 两个不同质数的乘积：如果 p, q 是两个不同质数，那么 p×q 的因数是 1, p, q, p×q，共4个
基本解法是对每个数暴力枚举所有因数，时间复杂度较高。
优化解法：只需遍历到数字的平方根即可找到所有因数。对于每个数 n：
- 从 1 遍历到 √n
- 如果 i 能整除 n，则 i 和 n/i 都是因数
- 需要注意 i = √n 时避免重复计算
具体步骤：
- 对数组中每个数字，计算其因数个数和因数之和
- 如果因数个数恰好是4，则将因数之和加入结果
- 返回总和
这种方法的时间复杂度是 O(n × √max(nums))，其中 n 是数组长度。
代码实现
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int totalSum = 0;
for (int num : nums) {
int divisorCount = 0;
int divisorSum = 0;
// 只需要遍历到平方根
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) {
divisorCount++;
divisorSum += i;
// 如果i不是平方根，还要加上num/i
if (i * i != num) {
divisorCount++;
divisorSum += num / i;
}
}
// 提前剪枝：如果因数超过4个就不用继续了
if (divisorCount > 4) break;
}
// 如果恰好有4个因数，加入总和
if (divisorCount == 4) {
totalSum += divisorSum;
}
}
return totalSum;
}
};
class Solution:
def sumFourDivisors(self, nums: List[int]) -> int:
total_sum = 0
for num in nums:
divisor_count = 0
divisor_sum = 0
# 只需要遍历到平方根
i = 1
while i * i <= num:
if num % i == 0:
divisor_count += 1
divisor_sum += i
# 如果i不是平方根，还要加上num//i
if i * i != num:
divisor_count += 1
divisor_sum += num // i
# 提前剪枝：如果因数超过4个就不用继续了
if divisor_count > 4:
break
i += 1
# 如果恰好有4个因数，加入总和
if divisor_count == 4:
total_sum += divisor_sum
return total_sum
public class Solution {
public int SumFourDivisors(int[] nums) {
int totalSum = 0;
foreach (int num in nums) {
int divisorCount = 0;
int divisorSum = 0;
// 只需要遍历到平方根
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) {
divisorCount++;
divisorSum += i;
// 如果i不是平方根，还要加上num/i
if (i * i != num) {
divisorCount++;
divisorSum += num / i;
}
}
// 提前剪枝：如果因数超过4个就不用继续了
if (divisorCount > 4) break;
}
// 如果恰好有4个因数，加入总和
if (divisorCount == 4) {
totalSum += divisorSum;
}
}
return totalSum;
}
}
var sumFourDivisors = function(nums) {
function getDivisors(n) {
let divisors = [];
for (let i = 1; i * i <= n; i++) {
if (n % i === 0) {
divisors.push(i);
if (i !== n / i) {
divisors.push(n / i);
}
}
}
return divisors;
}
let sum = 0;
for (let num of nums) {
let divisors = getDivisors(num);
if (divisors.length === 4) {
sum += divisors.reduce((a, b) => a + b, 0);
}
}
return sum;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n × √max(nums)) | n 是数组长度，需要对每个数计算因数，每次计算需要 O(√num) 时间 |
| 空间复杂度 | O(1) | 只使用了常数个变量存储中间结果 |