1. 題目

給你一個(gè)整數(shù)數(shù)組 nums，請(qǐng)你返回該數(shù)組中恰有四個(gè)因數(shù)的這些整數(shù)的各因數(shù)之和。

如果數(shù)組中不存在滿足題意的整數(shù)，則返回 0 。

示例： 輸入：nums = [21,4,7] 輸出：32 解釋： 21 有 4 個(gè)因數(shù)：1, 3, 7, 21 4 有 3 個(gè)因數(shù)：1, 2, 4 7 有 2 個(gè)因數(shù)：1, 7 答案僅為 21 的所有因數(shù)的和。提示： 1 <= nums.length <= 10^4 1 <= nums[i] <= 10^5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/four-divisors
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 直接模擬從2到 n/2，當(dāng)n很大的時(shí)候很耗時(shí)

class Solution { public:int sumFourDivisors(vector<int>& nums) {int sum = 0;pair<bool,int> p;for(int i = 0; i < nums.size(); ++i){p = isfour(nums[i]);if(p.first)sum += p.second;}return sum;}pair<bool, int> isfour(int &n){if(n == 1)return {false, 0};int count = 2;int divs = 1+n;for(int i = 2; i <= n/2; ++i){if(n%i == 0){count++;divs += i;}if(count > 4)return {false,0};}return {count==4,divs};} };

• 由于因數(shù)成對(duì)出現(xiàn)，所以從2遍歷到 $\sqrt{n}$ 即可
• 注意一對(duì)因數(shù)是相同的情況

class Solution { public:int sumFourDivisors(vector<int>& nums) {int sum = 0;pair<bool,int> p;for(int i = 0; i < nums.size(); ++i){p = isfour(nums[i]);if(p.first)sum += p.second;}return sum;}pair<bool, int> isfour(int &n){if(n == 1)return {false, 0};int count = 2;int divs = 1+n;for(int i = 2; i <= sqrt(n); ++i){if(n%i == 0){if(i != n/i){count += 2;divs += i+n/i;}else{count += 1;divs += i;}}if(count > 4)return {false,0};}return {count==4,divs};} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1390. 四因数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。