План курса / Все задачи / Алгоритмы и структуры данных
Богатый инвестор
легко
# решено
Дан массив price и число k. Найдите суммы всех k подряд идущих чисел.
Пример 1:
Ввод: price = [1,2,3,4,5,6], k = 2
Вывод: [3,5,7,9,11]
Пример 2:
Ввод: price = [-100,2], k = 1
Вывод: [-100,2]
Пример 3:
Ввод: price = [1,8,9], k = 5
Вывод: []
Ограничения:
len(price) ≥ 0
k ≥ 1
Значение массива price лежит в диапазоне [-10 000, 10 000] (включительно)
public class Solution {
public static List<int> KElementsSum(List<int> price, int k) {
if (k > price.Count) {
return new List<int>();
}
// firstSum - сумма первых k элементов
int firstSum = 0;
for (int i = 0; i < k; i++) {
firstSum += price[i];
}
// добавляем сумму первых k элементов к ответу
List<int> result = new List<int> { firstSum };
// r - индекс элемента, который добавляем к плавающему окну
for (int r = k; r < price.Count; r++) {
// l - индекс элемента, который убираем из плавающего окна
int l = r - k;
// вычисляем новую сумму плавающего окна
int nextSum = result[result.Count - 1] + price[r] - price[l];
// добавляем сумму к ответу
result.Add(nextSum);
}
return result;
}
}
#include <vector>
using namespace std;
vector<int> kElementsSum(vector<int>& price, int k) {
if (k > price.size()) {
return {};
}
// firstSum - сумма первых k элементов
int firstSum = 0;
for (int i = 0; i < k; i++) {
firstSum += price[i];
}
// добавляем сумму первых k элементов к ответу
vector<int> result = {firstSum};
// r - индекс элемента, который добавляем к плавающему окну
for (int r = k; r < price.size(); r++) {
// l - индекс элемента, который убираем из плавающего окна
int l = r - k;
// вычисляем новую сумму плавающего окна
int nextSum = result.back() + price[r] - price[l];
// добавляем сумму к ответу
result.push_back(nextSum);
}
return result;
}
package main
func kElementsSum(price []int, k int) []int {
if k > len(price) {
return []int{}
}
// firstSum - сумма первых k элементов
firstSum := 0
for i := 0; i < k; i++ {
firstSum += price[i]
}
// добавляем сумму первых k элементов к ответу
result := []int{firstSum}
// r - индекс элемента, который добавляем к плавающему окну
for r := k; r < len(price); r++ {
// l - индекс элемента, который убираем из плавающего окна
l := r - k
// вычисляем новую сумму плавающего окна
nextSum := result[len(result)-1] + price[r] - price[l]
// добавляем сумму к ответу
result = append(result, nextSum)
}
return result
}
import java.util.*;
public class Solution {
public static List<Integer> kElementsSum(List<Integer> price, int k) {
if (k > price.size()) {
return new ArrayList<>();
}
// firstSum - сумма первых k элементов
int firstSum = 0;
for (int i = 0; i < k; i++) {
firstSum += price.get(i);
}
// добавляем сумму первых k элементов к ответу
List<Integer> result = new ArrayList<>();
result.add(firstSum);
// r - индекс элемента, который добавляем к плавающему окну
for (int r = k; r < price.size(); r++) {
// l - индекс элемента, который убираем из плавающего окна
int l = r - k;
// вычисляем новую сумму плавающего окна
int nextSum = result.get(result.size() - 1) + price.get(r) - price.get(l);
// добавляем сумму к ответу
result.add(nextSum);
}
return result;
}
}
import java.util.*;
public class Solution {
public static List<Integer> kElementsSum(List<Integer> price, int k) {
if (k > price.size()) {
return new ArrayList<>();
}
// firstSum - сумма первых k элементов
int firstSum = 0;
for (int i = 0; i < k; i++) {
firstSum += price.get(i);
}
// добавляем сумму первых k элементов к ответу
List<Integer> result = new ArrayList<>();
result.add(firstSum);
// r - индекс элемента, который добавляем к плавающему окну
for (int r = k; r < price.size(); r++) {
// l - индекс элемента, который убираем из плавающего окна
int l = r - k;
// вычисляем новую сумму плавающего окна
int nextSum = result.get(result.size() - 1) + price.get(r) - price.get(l);
// добавляем сумму к ответу
result.add(nextSum);
}
return result;
}
}
from typing import *
def k_elements_sum(price: List[int], k: int) -> List[int]:
if k > len(price):
return []
# firstSum - сумма первых k элементов
firstSum = 0
for i in range(k):
firstSum += price[i]
# добавляем сумму первых k элементов к ответу
result = [firstSum]
# r - индекс элемента, который добавляем к плавающему окну
for r in range(k, len(price)):
# l - индекс элемента, который убираем из плавающего окна
l = r - k
# вычисляем новую сумму плавающего окна
nextSum = result[-1] + price[r] - price[l]
# добавляем сумму к ответу
result.append(nextSum)
return result
Оценка сложности
Время: O(n), где n - длина массива price
Память: O(n-k), где n - длина массива price; k - число подряд идущих элементов, которые нужно суммировать