Учитывая массив
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
Шаблон монстра:
если вам нравится этот шаблон, поделитесь им, чтобы люди могли его увидеть