Учитывая массив nums. Мы определяем текущую сумму массива как runningSum[i] = sum(nums[0]…nums[i]).

Вернуть текущую сумму nums.

Объяснение :

проблема просит нас создать новый массив (ans), и для каждого индекса i в этом массиве мы устанавливаем значение в этом индексе как сумму элементов в исходном массиве от индекса 0 до индекса i

Пример 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Пример 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Подход 1 (наивный):

Самый простой способ решить эту проблему — перебрать все индексы нового массива и для каждого индекса (назовем его i) сделать внутренний цикл, вычисляющий сумму элементов исходного массива от индекса 0 до индекса i и сохраните эту сумму в индексе i в новом массиве

Сложность: внешний цикл выполняет O(N) итераций, а внутренний цикл выполняет O(N) для каждой итерации, поэтому общая сложность составляет O(N * N), что очень плохо, даже если он проходит лимит времени

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        int numsSize=nums.size(), sum;
        vector<int> ans(numsSize);
        ans[0]=nums[0];
        for(int i=1;i<numsSize;i++)
        {
            sum=0;
            for(int j=0;j<=i;j++)
            {
                sum+=nums[j];
            }
            ans[i]=sum;
        }
        return ans;
    }
};

Подход 2:

если вы внимательно посмотрите на объяснение GIF первого примера, вы заметите, что нам не нужно вычислять сумму элементов от индекса 0 до индекса i на каждой итерации, потому что у нас уже есть сумма от индекса 0 до индекса i- 1, поэтому мы можем добавить его originalArray[i] и их сумма равна сумме элементов от индекса 0 до индекса i, так что теперь нам не нужен внутренний цикл и нам даже не нужно делать дополнительный массив для этот подход, потому что мы можем сохранить значение в том же исходном массиве, и причина, по которой он работает, заключается в том, что когда мы сохраняем новое значение в originalArray[i], нам не нужно его старое значение, поэтому нет никакого вреда от его замены.

Сложность: внешний цикл занимает O(N) итераций, и теперь нет внутреннего цикла, поэтому общая сложность составляет O(N)

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        int numsSize=nums.size();
        for(int i=1;i<numsSize;i++)
            nums[i]=nums[i-1]+nums[i];
        return nums;
    }
};

Если вам нравится этот пост, пожалуйста, поделитесь им, чтобы другие люди могли его увидеть, и если у вас есть какие-либо комментарии или вопросы, пожалуйста, не стесняйтесь обращаться ко мне.

Социальные сети:

Linkedin: Ахмед Мохаммед | LinkedIn

Шаблон монстра:

Flex — HTML-шаблон личного портфолио

если вам нравится этот шаблон, поделитесь им, чтобы люди могли его увидеть