Leetcode - 303. Range Sum Query - Immutable

문제

배열이 주어지고, (left, right) 인덱스를 가진 쿼리가 들어오면, left 부터 right까지의 합을 리턴하라.

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

해결 아이디어

• brute-force - O(n)
  sumRange가 호출될때마다 left 부터 right까지 항상 더하기
• O(1)
  초기화할때 i 까지의 부분합을 해시테이블에 저장. 그리고 left 부터 right까지의 합은 presum[right] - presum[left - 1] 이 됨.

0 1 2 3 4 5
    ^^^^^

2 ~ 4 까지의 합 -> presum[4] - presum[1]

풀이

class NumArray {
public:
    unordered_map<int, int> presum;
    NumArray(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            presum[i] = sum;
        }
    }
    
    int sumRange(int left, int right) {
        if (left == 0)
            return presum[right];
        return presum[right] - presum[left - 1];
    }
};