[leetcode #303] Range Sum Query - Immutable

Problem

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
Implement the NumArray class:

NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Constraints:

・ 1 <= nums.length <= 10⁴
・ -10⁵ <= nums[i] <= 10⁵
・ 0 <= left <= right < nums.length
・ At most 10⁴ calls will be made to sumRange.

Idea

Hard인 문제가 이틀 연속 나오니 오늘은 쉬운 문제가 나왔다. brute force로 풀면 nums의 길이가 10⁴, sumRange 함수 호출 수가 최대 10⁴이므로 덧셈을 10⁸번까지 수행할 수 있다. 이런 유형의 문제는 running sum을 사용하면 된다. running sum은 index 0부터 i까지의 합을 저장하는 것으로, running sum을 잘 사용하면 부분합을 쉽게 구할 수 있다.

(i번째 index에서 j번째 index까지의 부분합) = runningSum[j+1] - runningSum[i]

sumRange함수가 호출될 때마다 덧셈을 새로 수행하는 것이 아니라 미리 계산한 runningSum을 사용해 값을 리턴하는 방식으로 쉽게 풀 수 있다.

Solution

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

    public int sumRange(int left, int right) {
        return runningSum[right+1] - runningSum[left];
    }
}

Reference

https://leetcode.com/problems/range-sum-query-immutable/