LEETCODE 1390. Four Divisors 解题思路分析

题目大意：

四因数

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数，则返回 0 。

示例：

输入：nums = [21,4,7]
输出：32
解释：
 21 有 4 个因数：1, 3, 7, 21
 4 有 3 个因数：1, 2, 4
 7 有 2 个因数：1, 7
 答案仅为 21 的所有因数的和。

提示：

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1390

解题思路分析：

本题没有投机取巧的办法，我们必须求出数组中每一个数字的因数个数，然后再将因数个数为4的所有因数和累加至返回结果。

本题唯一需要强调的一个知识点是如何求一个数字num的质数个数。理论上最笨的方式是从1遍历至num，看num与哪些数字的余数为0即可，但这种做法明显效率不高。其实，当i是num的一个因子时，那么num/i也一定是num的另一个因子，比如3是27的一个因子，那么27/3=9也是27的一个因子，我们实际上同时找到了2个因子。不过唯一的例外是当因子是数字的平方根时，比如3是9的一个因子，这时 9/3 同样还是3，这时我们实际上只找到了一个因子而已。因此循环时，我们只需要从1循环至num的平方根即可，比如数字9，我们只要从1循环至3，就能遍历出9的所有因子。

实现代码：

public int sumFourDivisors(int[] nums) {
    int res=0; // 返回结果
    // 循环每一个数字，将其因子和加入返回结果
    for(int num : nums){
        res+=sumDivisors(num);
    }
    return res;
}
// 计算数字num的因子和
// 如果数字num不是正好包含4个因子，返回0
int sumDivisors(int num){
    // 数字num的平方根
    int sqrt=(int)Math.sqrt(num);
    // 因子个数
    int count=0;
    // 因子和
    int sum=0;
    // 从1循环至num的平方根
    for(int i=1;i<=sqrt;i++){
        // 如果num与i的余数为0。
        if(num%i==0) {
            // 如果num与i的商等于i，说明我们找到了1个因子
            if(num/i==i){
                count+=1;
                sum+=i;
            }else{ 我们找到了2个因子
                count+=2;
                sum+=(i+num/i);
            }
            if(count>4) break;
        }
    }
    // 当因子数为4时，返回因子的和，反之返回0
    return count==4?sum:0;
}

本题解法执行时间为13ms。

Runtime: 13 ms, faster than 92.85% of Java online submissions for Four Divisors.

Memory Usage: 41.5 MB, less than 100.00% of Java online submissions for Four Divisors.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1390-four-divisors-解题思路分析/