LeetCode 1390. 四因数

Categories:

题目描述
思路分析
1. 解法一：枚举因子（推荐）
相似题目

题目描述

✅ 1390. 四因数

思路分析

解法一：枚举因子（推荐）

核心思路：

对每个数枚举到平方根，成对收集因子。

若因子数量恰好为 4，则累加这 4 个因子之和。

超过 4 个则提前停止。

复杂度分析：

时间复杂度：O(n * sqrt(C))，C 为最大元素。

空间复杂度：O(1)。

class Solution {
    public int sumFourDivisors(int[] nums) {
        int total = 0;
        for (int x : nums) {
            int sum = 0;
            int count = 0;
            for (int d = 1; d * d <= x; d++) {
                if (x % d != 0) {
                    continue;
                }
                int d1 = d;
                int d2 = x / d;
                if (d1 == d2) {
                    count++;
                    sum += d1;
                } else {
                    count += 2;
                    sum += d1 + d2;
                }
                if (count > 4) {
                    break;
                }
            }
            if (count == 4) {
                total += sum;
            }
        }
        return total;
    }
}

func sumFourDivisors(nums []int) int {
    total := 0
    for _, x := range nums {
        sum := 0
        count := 0
        for d := 1; d*d <= x; d++ {
            if x%d != 0 {
                continue
            }
            d1 := d
            d2 := x / d
            if d1 == d2 {
                count++
                sum += d1
            } else {
                count += 2
                sum += d1 + d2
            }
            if count > 4 {
                break
            }
        }
        if count == 4 {
            total += sum
        }
    }
    return total
}

相似题目

题目	难度	考察点
2427. 公因子的数目	简单	因子
507. 完美数	简单	因子
204. 计数质数	简单	数论
1175. 质数排列	简单	数论
1362. 最接近的因数	中等	因子

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/71219341