时间戳

首页 > 解决方案 > 你能建议我优化这段代码的方法吗？

c++ - 你能建议我优化这段代码的方法吗？

问题描述

下面是问题问题。
https://leetcode.com/problems/four-divisors/

我需要更优化的代码。以下代码超出时间限制。请建议我进行一些编辑以使此代码更优化。

我的解决方案：

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        vector<int> ans;
        int x=0;

        for(int i=0;i<nums.size();i++){
            int j=1;
            while(j!=nums[i]+1){
                if(nums[i]%j==0){
                    ans.push_back(j);

                }
                j++;
            }

                if(ans.size()==4){
                     x=accumulate(ans.begin(),ans.end(),x);
                     ans.clear();


                }
               else
                   ans.clear();

         }
        return x;
    }
};

标签： c++c++11

解决方案

像这样的问题的诀窍是找到比明显的蛮力方法做更少的工作的方法。对于 中的每个数字nums[i]，nums您都在进行nums[i]模运算。有一些方法可以显着减少这个数字。当你试图加速重复做同样事情的代码时，你有两个选择：1）加速每次迭代；2）减少所需的迭代次数。如果您无法通过一种方法取得很大进展，请尝试另一种方法。

既然做这样的问题是为了更好地解决问题，我不认为告诉你问题的答案是正确的做法。即便如此，举个例子来说明我在说什么，并没有给出太多的帮助。

假设其中一个数字nums是 24。现在，您的程序计算从 1 到 24nums[i]%j的所有数字j。但是您知道 1 并且nums[i]始终是除数，因此一旦找到24 % 2 == 0和24 % 3 == 0，您就已经有四个除数了。当你到达时，24 % 4 == 0你已经有 5 个除数，所以你知道你可以跳过 24，因为它有超过 4 个除数。尽快退出可以节省大量浪费的工作。

所以，使用你所知道的来减少你的代码所做的工作量。在这个问题中还有其他几种方法可以做到这一点，实际上最佳解决方案甚至不需要上面的显式检查。即使对于大数字，检查每个数字所需的 mod 操作数也将远小于数字本身。

推荐阅读