Дан массив чисел. Сумма элементов массива по текущему индексу определяется следующим образом: runningSum[i] = sum(nums[0]…nums[i]).
Верните текущую сумму чисел.
Пример 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Текущая сумма получается следующим образом: [1, 1+2, 1+2+3, 1+2+3+4].Пример 2:
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Текущая сумма получается следующим образом: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].Пример 3:
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]Решение
Если рассматривать задачу в лоб, то можно было бы написать цикл от 0 до n, в котором был бы еще один цикл от 0 до i. В последнем цикле мы бы считали сумму всех чисел. Выглядело бы это примерно так:
class Solution {
func runningSum(_ nums: [Int]) -> [Int] {
var result: [Int] = []
var sum = 0
for i in num {
var sum = 0
for j in 0..<i {
sum += num[j]
}
result.append(sum)
}
return result
}
}И в целом, задача была бы решена, но сложность такого подхода — O(n2).
Давайте улучшим наш алгоритм: так как нам необходимо вернуть сумму элементов массива до текущего индекса, то мы по факту всегда производим операцию сложения на каждой итерации цикла. То есть мы можем на каждой итерации цикла записывать ответ по текущему индексу:
class Solution {
func runningSum(_ nums: [Int]) -> [Int] {
var result: [Int] = []
var sum = 0
for i in num {
sum += num[i-1]
result.append(sum)
}
return result
}
}Сложность такого алгоритма — O(n)!
Мы значительно улучшили наш алгоритм, давайте еще немного оптимизируем наш код:
class Solution {
func runningSum(_ nums: [Int]) -> [Int] {
var result: [Int] = []
result.append(nums[0])
for i in 1..<nums.count {
result.append(result[i-1] + nums[i])
}
return result
}
}Дополнительный материал
Выразить благодарность или найти уникальный материал вы можете в boosty.
Подписывайтесь на мой Telegram-канал iOS Interview Channel, чтобы не пропустить новый материал.
Похожие сообщения
-
Максимальная сумма элементов ряда двумерного массива
15 октября, 2023
