LeetCode - 303. Range Sum Query

문제

---

풀이

가장 기초적인 DP 문제이다.

0부터 배열의 끝까지의 합을 구한 배열을 하나 선언하여, sumRange 함수가 호출 될 때 사용하면 된다.

sum 배열은 0 ~ num.length + 1 값이 존재하며, sum[i]는 num[0]~num[i-1]까지의 합을 의미한다.

따라서 sumRange(i,j)는 sum[j + 1] - sum[i]를 반환하면 원하는 결과를 얻을 수 있다.

---

코드

class NumArray {
    int []nums;
    int []sum;

    public NumArray(int[] nums) {
        this.nums = nums;
        sum = new int[nums.length + 1];

        for(int i=1;i<=nums.length;i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }
    }

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

---