В этом уроке ты
- Освоишь технику «префиксный массив».
- Решишь задачу с реального собеседования.
- Научишься вычислять сумму на отрезке за O(1), чтобы уверенно пройти интервью.
Пример задачи с собеседования
Представь, что ты пришёл на собеседование. Интервьюер уже ждёт тебя и озвучивает условие задачи…
Условие
Реализуй структуру данных, которая позволяет быстро находить сумму всех элементов на отрезке [l, r] (включая границы). При этом массив не изменяется.
Другими словами, нужно реализовать:
- Конструктор (вызывается один раз).
- Метод
sum(вызывается многократно, поэтому он должен быть максимально быстрым).
public class PrefixArray {
// Конструктор
public PrefixArray(int[] nums) {
// Нужно реализовать
}
// Метод для нахождения суммы
public int sum(int left, int right) {
// Нужно реализовать
}
}#include <vector>
using namespace std;
class PrefixArray {
public:
// Конструктор
PrefixArray(const vector<int>& nums) {
// Нужно реализовать
}
// Метод для нахождения суммы
int sum(int left, int right) {
// Нужно реализовать
}
};package main
type PrefixArray struct {}
func NewPrefixArray(nums []int) *PrefixArray {
// Нужно реализовать
}
func (p *PrefixArray) Sum(left, right int) int {
// Нужно реализовать
}import java.util.ArrayList;
import java.util.List;
class PrefixArray {
// Конструктор
public PrefixArray(int[] nums) {
// Нужно реализовать
}
// Метод для нахождения суммы
public int sum(int left, int right) {
// Нужно реализовать
}
}
from typing import *
class PrefixArray:
def __init__(self, nums: List[int]):
# Нужно реализовать
def sum(self, left: int, right: int) -> int:
# Нужно реализоватьexport class PrefixArray {
constructor(nums) {
// Нужно реализовать
}
// Метод для нахождения суммы
sum(left, right) {
// Нужно реализовать
}
}Пример
Ввод: nums = [1, 4, 5, -3, 7, 2] l = 0, r = 2 l = 0, r = 5 l = 3, r = 5 Вывод: 10 16 6
В чем сложность задачи?
Кандидат, который торопится скорее написать код, может не обратить внимание на важную формулировку в условии: “быстро находить сумму всех элементов на отрезке”, и напишет такое решение:
public class PrefixArray {
private int[] prefix;
// Конструктор
public PrefixArray(int[] nums) {
prefix = nums;
}
// Метод для нахождения суммы
public int sum(int left, int right) {
int total = 0;
for (int i = left; i <= right; i++)
{
total = total + prefix[i];
}
return total;
}
}#include <vector>
using namespace std;
class PrefixArray {
public:
// Время: O(n), где n — число элементов в nums
// Память: O(n)
PrefixArray(const vector<int>& nums) : nums(nums) {}
// Время: O(right - left)
// Память: O(1)
int sum(int left, int right) const {
int total = 0;
for (int i = left; i <= right; ++i) {
total += nums[i];
}
return total;
}
private:
vector<int> nums;
};package main
import "fmt"
type PrefixArray struct {
nums []int
}
// Время: O(n), где n — число элементов в nums
// Память: O(n)
func NewPrefixArray(nums []int) *PrefixArray {
return &PrefixArray{nums: nums}
}
// Время: O(right - left)
// Память: O(1)
func (p *PrefixArray) Sum(left int, right int) int {
total := 0
for i := left; i <= right; i++ {
total += p.nums[i]
}
return total
}import java.util.List;
class PrefixArray {
// Время: O(n), где n — число элементов в nums
// Память: O(n)
private List<Integer> nums;
public PrefixArray(int[] nums) {
this.nums = nums;
}
// Время: O(right - left)
// Память: O(1)
public int sum(int left, int right) {
int total = 0;
for (int i = left; i <= right; i++) {
total += nums.get(i);
}
return total;
}
}from typing import *
class PrefixArray:
# Время: O(n), где n — число элементов в nums
# Память: O(n)
def __init__(self, nums: List[int]):
self.nums = nums
# Время: O(right - left)
# Память: O(1)
def sum(self, left: int, right: int) -> int:
return sum(self.nums[left:right+1])class PrefixArray {
// Время: O(n), где n — число элементов в nums
// Память: O(n)
constructor(nums) {
this.nums = nums;
}
// Время: O(right - left)
// Память: O(1)
sum(left, right) {
let total = 0;
for (let i = left; i <= right; i++) {
total += this.nums[i];
}
return total;
}
}Метод sum каждый раз пересчитывает сумму элементов с индекса left до right и работает не оптимально по времени: за O(right - left).
Оптимальное решение
Чтобы избежать пересчёта сумм элементов, воспользуемся техникой префиксного массива:
public class PrefixArray {
private int[] prefix;
// Конструктор
public PrefixArray(int[] nums) {
prefix = new int[nums.Length + 1];
prefix[0] = 0;
for (int i = 0; i < nums.Length; i++)
{
prefix[i + 1] = prefix[i] + nums[i];
}
}
// Метод для нахождения суммы
public int sum(int left, int right) {
return prefix[right + 1] - prefix[left];
}
}#include <vector>
using namespace std;
class PrefixArray {
public:
vector<int> prefix;
// Конструктор
PrefixArray(const vector<int>& nums) {
// создаем префиксный массив
prefix.push_back(0);
for (int num : nums) {
prefix.push_back(prefix.back() + num);
}
}
// Метод для нахождения суммы
int sum(int left, int right) {
// находим сумму, используя префиксный массив
return prefix[right + 1] - prefix[left];
}
};package main
type PrefixArray struct {
prefix []int
}
// Конструктор
func NewPrefixArray(nums []int) *PrefixArray {
p := &PrefixArray{prefix: []int{0}}
// создаем префиксный массив
for _, num := range nums {
p.prefix = append(p.prefix, p.prefix[len(p.prefix)-1]+num)
}
return p
}
// Метод для нахождения суммы
func (p *PrefixArray) Sum(left, right int) int {
// находим сумму, используя префиксный массив
return p.prefix[right+1] - p.prefix[left]
}import java.util.ArrayList;
import java.util.List;
class PrefixArray {
private List<Integer> prefix;
// Конструктор
public PrefixArray(int[] nums) {
prefix = new ArrayList<>();
prefix.add(0); // Добавляем начальное значение 0
for (int num : nums) {
prefix.add(prefix.get(prefix.size() - 1) + num);
}
}
// Метод для нахождения суммы
public int sum(int left, int right) {
// Находим сумму, используя префиксный массив
return prefix.get(right + 1) - prefix.get(left);
}
}from typing import *
class PrefixArray:
def __init__(self, nums: List[int]):
# создаем префиксный массив
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
return
def sum(self, left: int, right: int) -> int:
# находим сумму, используя префиксный массив
return self.prefix[right + 1] - self.prefix[left]class PrefixArray {
constructor(nums) {
// создаем префиксный массив
this.prefix = [0];
for (let num of nums) {
this.prefix.push(this.prefix[this.prefix.length - 1] + num);
}
}
// Метод для нахождения суммы
sum(left, right) {
// находим сумму, используя префиксный массив
return this.prefix[right + 1] - this.prefix[left];
}
}В оптимальном решении метод sum работает за O(1), что именно и ожидает интервьюер.
Давай разберём, как это устроено!
Префиксные массивы
Допустим, у нас есть массив: nums = [1, 4, 5, -3, 7, 0, 2, 4]. Нужно найти сумму элементов на отрезке с индекса 2 по 6.
Зная сумму первых семи элементов (prefix[7]) и первых двух элементов (prefix[2]), получаем:
sum = prefix[7] − prefix[2] = 16 − 5 = 11
Такой подход намного быстрее, чем пересчёт всех элементов вручную: 5 + (-3) + 7 + 0 + 2 = 11
Имея заранее посчитанные суммы, можно очень быстро находить сумму на отрезках, а именно за O(1).
Строим префиксный массив
Префиксный массив содержит накопленные суммы элементов исходного массива:
- Первый элемент равен
0. - Каждый следующий — это сумма всех предыдущих элементов.
Например, для массива nums = [1, 4, 5, -3, 7, 0, 2, 4]
prefix = [0, 1, 5, 10, 7, 14, 14, 16, 20]
Построить префиксный массив достаточно просто:
public class PrefixArray {
private int[] prefix;
// Конструктор
public PrefixArray(int[] nums) {
prefix = new int[nums.Length + 1];
prefix[0] = 0;
for (int i = 0; i < nums.Length; i++)
{
prefix[i + 1] = prefix[i] + nums[i];
}
}
}#include <vector>
using namespace std;
class PrefixArray {
public:
vector<int> prefix;
PrefixArray(const vector<int>& nums) {
// Создаём префиксный массив
prefix.push_back(0);
for (int num : nums) {
prefix.push_back(prefix.back() + num);
}
}
};#include <vector>
using namespace std;
class PrefixArray {
public:
vector<int> prefix;
PrefixArray(const vector<int>& nums) {
// Создаём префиксный массив
prefix.push_back(0);
for (int num : nums) {
prefix.push_back(prefix.back() + num);
}
}
};import java.util.ArrayList;
import java.util.List;
class PrefixArray {
private List<Integer> prefix;
public PrefixArray(int[] nums) {
// Создаём префиксный массив
prefix = new ArrayList<>();
prefix.add(0);
for (int num : nums) {
prefix.add(prefix.get(prefix.size() - 1) + num);
}
}
}from typing import *
class PrefixArray:
def __init__(self, nums: List[int]):
# Создаём префиксный массив
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)class PrefixArray {
constructor(nums) {
// создаем префиксный массив
this.prefix = [0];
for (let num of nums) {
this.prefix.push(this.prefix[this.prefix.length - 1] + num);
}
}
}Префиксный массив в действии
Чтобы найти сумму элементов массива nums с индекса L = 1 до R = 6, используем формулу:
sum = prefix[R + 1] - prefix[L]
Почему префиксный массив начинается с 0?
Дополнительный 0 спасает нас от выхода за границу массива. Даже если L = 0 и R = 7, всё будет корректно в формуле sum = prefix[R + 1] - prefix[L].
В итоге, мы получаем полную реализацию префиксного массива, которая работает оптимально:
public class PrefixArray {
private int[] prefix;
// Конструктор
public PrefixArray(int[] nums) {
prefix = new int[nums.Length + 1];
prefix[0] = 0;
for (int i = 0; i < nums.Length; i++)
{
prefix[i + 1] = prefix[i] + nums[i];
}
}
// Метод для нахождения суммы
public int sum(int left, int right) {
return prefix[right + 1] - prefix[left];
}
}#include <vector>
using namespace std;
class PrefixArray {
public:
vector<int> prefix;
// Конструктор
PrefixArray(const vector<int>& nums) {
// создаем префиксный массив
prefix.push_back(0);
for (int num : nums) {
prefix.push_back(prefix.back() + num);
}
}
// Метод для нахождения суммы
int sum(int left, int right) {
// находим сумму, используя префиксный массив
return prefix[right + 1] - prefix[left];
}
};package main
type PrefixArray struct {
prefix []int
}
// Конструктор
func NewPrefixArray(nums []int) *PrefixArray {
p := &PrefixArray{prefix: []int{0}}
// создаем префиксный массив
for _, num := range nums {
p.prefix = append(p.prefix, p.prefix[len(p.prefix)-1]+num)
}
return p
}
// Метод для нахождения суммы
func (p *PrefixArray) Sum(left, right int) int {
// находим сумму, используя префиксный массив
return p.prefix[right+1] - p.prefix[left]
}import java.util.ArrayList;
import java.util.List;
class PrefixArray {
private List<Integer> prefix;
// Конструктор
public PrefixArray(int[] nums) {
prefix = new ArrayList<>();
prefix.add(0); // Добавляем начальное значение 0
for (int num : nums) {
prefix.add(prefix.get(prefix.size() - 1) + num);
}
}
// Метод для нахождения суммы
public int sum(int left, int right) {
// Находим сумму, используя префиксный массив
return prefix.get(right + 1) - prefix.get(left);
}
}from typing import *
class PrefixArray:
def __init__(self, nums: List[int]):
# создаем префиксный массив
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
return
def sum(self, left: int, right: int) -> int:
# находим сумму, используя префиксный массив
return self.prefix[right + 1] - self.prefix[left]class PrefixArray {
constructor(nums) {
// создаем префиксный массив
this.prefix = [0];
for (let num of nums) {
this.prefix.push(this.prefix[this.prefix.length - 1] + num);
}
}
// Метод для нахождения суммы
sum(left, right) {
// находим сумму, используя префиксный массив
return this.prefix[right + 1] - this.prefix[left];
}
}Что дальше
Не теряй время и переходи к решению практических задач — это позволит тебе закрепить свои знания.
Так ты сможешь быстро и уверенно справляться с трудными вопросами на собеседовании!