Leetcode 1390:四因数(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1390:四因数(超详细的解法!!!)

in leetcode with 0 comment

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

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

示例:

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

提示:

解题思路

比较容易写出暴力解法,也就是计算每个数的因子,然后累加只有四个因子的所有数的因子和。然后如何获取因子呢?暴力枚举。

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        def get_divisors(x):
            res, i = [], 1
            while i * i <= x:
                if x % i == 0:
                    res.append(i)
                    if i * i != x: res.append(x // i)
                    if len(res) > 4: return 0
                i += 1
            return 0 if len(res) < 4 else sum(res)
        
        return sum(get_divisors(v) for v in nums)

为了操作速度更快,我们可以使用变量统计因子个数,而不是通过数组存储因子。

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        def get_divisors(x):
            res, cnt, i = 0, 0, 1
            while i * i <= x:
                if x % i == 0:
                    res += i
                    cnt += 1
                    if i * i != x: 
                        res += x // i
                        cnt += 1
                    if cnt > 4: return 0
                i += 1
            return 0 if cnt < 4 else res
        
        return sum(get_divisors(v) for v in nums)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses