303. Range Sum Query - Immutable

leetcode easy

#array#csharp#design#easy#leetcode#two-pointers

Task

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:

Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.

Реализуйте класс NumArray:

- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.

- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input

["NumArray", "sumRange", "sumRange", "sumRange"]

[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output

[null, 1, -1, -3]

C# solution

matched/original

public class NumArray {
    private int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.Length + 1];
        for (int i = 0; i < nums.Length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }
    public int SumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class NumArray {
    private vector<int>& sum;
    public NumArray(vector<int>& nums) {
        sum = new int[nums.size() + 1];
        for (int i = 0; i < nums.size(); i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }
    public int SumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

Java solution

matched/original

public class NumArray {
    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

JavaScript solution

matched/original

class NumArray {
    constructor(nums) {
        this.sum = new Array(nums.length + 1).fill(0);
        for (let i = 0; i < nums.length; i++) {
            this.sum[i + 1] = this.sum[i] + nums[i];
        }
    }

    sumRange(i, j) {
        return this.sum[j + 1] - this.sum[i];
    }
}

Python solution

matched/original

class NumArray:
    def __init__(self, nums: List[int]):
        self.sum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.sum[i + 1] = self.sum[i] + nums[i]

    def sumRange(self, i: int, j: int) -> int:
        return self.sum[j + 1] - self.sum[i]

Go solution

matched/original

package main

type NumArray struct {
    sum []int
}

func Constructor(nums []int) NumArray {
    sum := make([]int, len(nums)+1)
    for i := 0; i < len(nums); i++ {
        sum[i+1] = sum[i] + nums[i]
    }
    return NumArray{sum}
}

func (this *NumArray) SumRange(i int, j int) int {
    return this.sum[j+1] - this.sum[i]
}

Explanation

Algorithm

Инициализация:

Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

Предварительное вычисление сумм:

Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

Вычисление диапазонной суммы:

Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎