题目描述

给你一个整数数组 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

算法分析

模拟

• 用试除法求出每个数的所有因数，若该数的因数个数刚好是4，则把所有的因数更新到答案中

时间复杂度 $O(n \sqrt n)$

Java 代码

class Solution {
    static List<Integer> get_divide(int x)
    {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 1;i <= x / i;i ++)
        {
            if(x % i == 0)
            {
                list.add(i);
                if(i != x / i) list.add(x / i);
            }
        }
        return list;
    }
    public int sumFourDivisors(int[] nums) {
        int n = nums.length;
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            List t = get_divide(nums[i]);
            if(t.size() == 4)
            {
                for(int j = 0;j < 4;j ++)
                {
                    res += (int)t.get(j);
                }
            }
        }
        return res;
    }   
}