本文主要是介绍leetcode-四因数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目是LeetCode第181场周赛的第二题，链接：四因数。具体描述为：给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。
示例:
输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。
很明显，有四个因数的数，其四个因数必然是1和它本身，再加上另外两个不相等的因数（也就是说像平方数这种必然不可能符合条件）。那么一种最简单的做法就是对于一个数n，遍历从2到 n \sqrt{n} n，记录可以整除n的数，出现一个便可以说明因数的数量+2（同时需要注意如果是 n \sqrt{n} n的话只用+1），因为有一个 m < n m<\sqrt{n} m<n可以整除n的话说明必然有另一个 n m > n \frac{n}{m}>\sqrt{n} mn>n也可以整除n。只要这样的因数的数量刚好为2，再加上1和n本身就构成了四个因数。假设数组的长度为N，其中最大的数为M，则时间复杂度为 O ( N M ) O(N\sqrt{M}) O(NM)，空间复杂度为 O ( 1 ) O(1) O(1)。
JAVA版代码如下：
class Solution {private int factorSum(int n) {int sqrtN = (int)Math.sqrt(n);int count = 0;int sum = 0;for (int i = 2; i <= sqrtN; ++i) {if (n % i == 0) {++count;int another = n / i;if (i != another) {sum = i + another;++count;}if (count > 2) {break;}}}if (count == 2) {return sum + 1 + n;}return 0;}public int sumFourDivisors(int[] nums) {int result = 0;for(int n : nums) {result += factorSum(n);}return result;}
}
提交结果如下:
Python版代码如下：
class Solution:def sumFourDivisors(self, nums: List[int]) -> int:def factor4num(n):sqrtN = (int)(math.sqrt(n))count = 0sum4factor = 0for i in range(2, sqrtN + 1):if n % i == 0:count += 1if i != n // i: #不能是平方根，否则不可能刚好有4个因数sum4factor += i + n // icount += 1if count > 2: #一定超过4个了breakif count == 2:return sum4factor + 1 + nreturn 0result = 0for n in nums:result += factor4num(n)return result
提交结果如下:
这篇关于leetcode-四因数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
