宿州市网站建设_网站建设公司_服务器部署_seo优化

题目链接：1390. 四因数（中等）

算法原理：

解法：记忆化枚举

28ms击败55.70%

时间复杂度O(n × √M)

对于一个数n最暴力的方法就是从1开始枚举到n，然后统计它有多少个因数，再进行累加，但这样的话时间复杂度会飙升到O(N²)，即使通过也会超时的

所以咱们可以在上面那个基础上逐渐优化👇

①咱只需找俩因数即可：因为一个数至少有俩因数，1和它本身，这就已经是俩因数了，因此咱们只需在它俩中间再找俩即可，所以逐个枚举时就可以从2开始枚举到n-1即可

②咱只需找一次因数即可：因为因数一定是成对出现的，

比如说针对21，枚举到3时会出现21÷3=7，这里3是21的因数，但同时7也是21的因数，因此咱们找一次因数即可，但这里有个细节，

比如说针对16，枚举到4时，会出现16÷4=4，但4只能算一个因数，因此这时累加时只能加一个

鉴于以上分析，我们就没必要从2遍历到n-1了，因为会算重复，所以咱们只需要遍历一半即可，即从2开始枚举到√n，这是时间复杂度的一个巨大的优化！

③备忘录优化：由于同一个数可能重复出现，因此当这个数第一次出现的时候就存进哈希表，下次遍历的时候就没必要重新算一遍了

答疑：

Q1：如果出现两个相同的因数的话，那么只能算一次吧，加上只能成为奇数啊，但是咱们要求的是4因数，是偶数，因数相同的时候咱就没必要算了啊，直接跳过呗

不可以，虽然不会少算，但会多算！

比如16的因数是1、2、4、8、16，如果直接把4跳过，会把16也算成四因数的数，导致结果偏大

Java代码：

class Solution { public int sumFourDivisors(int[] nums) { int ret=0; //建立备忘录 Map<Integer,Integer> hash=new HashMap<>(); for(int x:nums){ //先往备忘录里瞅瞅 if(hash.containsKey(x)){ ret+=hash.get(x); continue; } int count=0,sum=0; for(int i=2;i<=Math.pow(x,0.5);i++){ if(x%i==0&&i!=x/i){ count+=2; sum+=(i+x/i); }else if(x%i==0&&i==x/i){ count++; sum+=i; } if(count>2) break; } if(count==2){ hash.put(x,x+1+sum); ret+=(x+1+sum); } } return ret; } }