leetcode 1390

问题

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

1
2
3
4
5
6
7
Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Constraints:

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

分析

这道题的解题比较暴力，直接对数组中的每个数进行判断即可。当时做的时候一直觉得这样做可能是会超时的，没有正确地估计好时间复杂度，这也是记录下本题的一个主要的原因。在判断每个数 num 是否四个除数的时候只需要遍历到 $\sqrt{ num}$ 即可，时间复杂度为 $O(n\sqrt{ num})$，根据最大数量级的时间复杂度越为 $10^4 \sqrt{ 10^5} = 10^6 * \sqrt{10}$ 。是可以AC的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int ans = 0;
        for (int n: nums) {
            int last_d = 0;
            for (int d = 2; d*d <= n; ++d) {
                if ((n%d) == 0) {
                    if (last_d != 0) {
                        last_d = 0;
                        break;
                    } else {
                        last_d = d;
                    }
                }
            }
            if (last_d != 0 && n/last_d != last_d) {
                ans += 1 + n + last_d + n/last_d;
            }
        }
        return ans;
    }
};