这个题解的核心思路是通过遍历数组中的每个数字,并检查每个数字具有四个因数的情况。对每个数字,它首先尝试找到第一个小于其平方根的因数。如果找到这样的因数,它会尝试确定这个因数和剩余的商是否可以形成四个因数的组合。数学上,一个数字有四个因数的情况通常是它由两个不同的质因数组成(形如 p*q),或它是某个质数的三次方(形如 p^3)。对于每个数字的因数检查,如果符合四因数的条件,则计算这四个因数的和。为了避免重复计算,使用一个哈希表来存储已经计算过的数字及其因数之和。
时间复杂度: O(m*sqrt(n))
空间复杂度: O(m)
class Solution:
def sumFourDivisors(self, nums: List[int]) -> int:
table = {} # used to store the sums of divisors of numbers already checked
res = 0 # the final result sum
def FourDivSum(num):
i = 2
while i * i < num:
if num % i == 0:
break
i += 1
if i * i >= num:
return 0
if i ** 3 == num:
return sum([i ** j for j in range(4)]) # handles the case p^3
num = num // i
j = 2
while j * j <= num:
if num % j == 0:
break
j += 1
if j * j > num:
# handles the case p*q
return sum([1, i, num, i * num])
return 0
for num in nums:
if num in table:
res += table[num] # use cached result
continue
table[num] = FourDivSum(num) # calculate and store the sum of four divisors
res += table[num]
return res