Можете ли вы предложить мне способы оптимизации этого кода?

Question

Ниже приведен проблемный вопрос. 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;
    }
};

Answer 1

Хитрость для таких вопросов, как этот, заключается в том, чтобы найти способы сделать гораздо меньше работы, чем очевидный метод грубой силы. Для каждого числа nums[i] в nums вы выполняете nums[i] операции по модулю. Есть способы, которыми вы могли бы значительно сократить это число. Когда вы пытаетесь ускорить код, который повторяет одно и то же, у вас есть два варианта: 1) ускорить каждую итерацию; 2) уменьшить количество необходимых итераций. Если вы не можете добиться больших успехов с одним подходом, попробуйте другой.

Поскольку задача решения подобных проблем заключается в том, чтобы лучше справляться с решением проблем, я не думаю, что говорю вам ответ на проблему. это то, что нужно сделать. Тем не менее, это не слишком много, чтобы привести пример того, о чем я говорю.

Скажем, одно из чисел в nums равно 24. Сейчас ваша программа рассчитывает nums[i]%j для все j от 1 до 24. Но вы знаете, что 1 и nums[i] всегда являются делителями, поэтому, как только вы обнаружите, что 24 % 2 == 0 и 24 % 3 == 0, у вас уже есть четыре делителя. К тому времени, когда вы доберетесь до 24 % 4 == 0, у вас уже есть 5 делителей, так что вы знаете, что можете пропустить 24, потому что у него более 4 делителей. Выручение, как только вы можете сэкономить много потраченной впустую работы.

Итак, используйте то, что вы знаете , чтобы уменьшить объем работы, выполняемой вашим кодом. Есть несколько других способов сделать это в этой проблеме, и фактически оптимальное решение даже не потребует явной проверки выше. Даже для больших чисел количество операций мода, необходимых для проверки каждого числа, будет намного меньше, чем само число.