[LeetCode/Easy] 303. Range Sum Query - Immutable

목표: 배열의 부분 합을 계산하는 클래스 구현

- 생성자

- int sumRange(int left, int right)

 

1. Input

1) 생성자: int[] nums;

2) sumRange(): 부분 합을 구할 인덱스의 범위

 

2. Output

1) sumRange(): nums[left]부터 nums[right]까지의 합

 

3. Constraint

1) 1 <= nums.length <= 10^4

2) - 10^5 <= nums[i] <= 10^5

3) 0 <= left <= right < nums.length

4) sumRange는 만번까지 호출될 수 있다.

 

4. Example

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

 

5. Code

1) 첫 코드(2022/07/12)

class NumArray {
    int[] nums;
    
    public NumArray(int[] nums) {
        this.nums = nums;    
    }
    
    public int sumRange(int left, int right) {
        int sum = 0;
        for(int i=left ; i<=right ; i++)
            sum += nums[i];
        return sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */

- 너무 비효율적이라 나중에 다시 풀어보기로 했던 문제였다.

 

2) 다시 풀어본 코드(2023/05/18)

class NumArray {
    int[] presum;
    public NumArray(int[] nums) {
        presum = new int[nums.length];
        presum[0] = nums[0];
        for(int i=1 ; i<presum.length ; i++)
            presum[i] = presum[i-1] + nums[i];
    }
    
    public int sumRange(int left, int right) {
        int ans = presum[right];
        if(left>0)
            ans -= presum[left-1];
        return ans;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */