303. Range Sum Query - Immutable

description

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Constraints:

You may assume that the array does not change.
There are many calls to sumRange function.
0 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5
0 <= i <= j < nums.length

Solution

처음에는 DP 문제라고 분류는 되어 있었지만? 그렇게 풀지 않아도 될 것 같아서 아래와 같이 작성했다.

Code ver.1.0

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums

    def sumRange(self, i: int, j: int) -> int:
        rangeLength = j - i + 1
        sum = self.nums[i]
        
        for k in range(i+1,j+1) :
            sum += self.nums[k]
        
        return sum


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

Logic

단순하게 풀었다. i와 j를 포함하게끔 합을 구해서 리턴했다.

근데 이렇게 풀면 Time Complexity가 안좋게 나오는데 그 이유를 생각해보니 테케들을 돌릴 때마다 nums는 동일해도 합을 계속 구해야 하는 것 같았다. 그래서 DP를 적용해서 다시 풀어보았다.

Code ver.2.0

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.sumArr = [0] * len(nums)
        if (len(nums) > 0) :
            self.sumArr[0] = nums[0]
        
            for i in range(1,len(self.nums)) :
                self.sumArr[i] = self.sumArr[i-1] + self.nums[i]

    def sumRange(self, i: int, j: int) -> int:
        if (i==0): return self.sumArr[j]
        return self.sumArr[j] - self.sumArr[i-1]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

Logic

일단 nums가 빈 배열이라는 것을 고려하지 않으면 submit 했을 때 index range 에러가 발생한다. 빈 배열이 아닐 경우에는 DP를 이용해서 0부터 i번째까지의 sum을 구해놓는다.

그리고 sumRange 함수에서는 j번째 원소에서 i-1번째 원소를 뺀다. 단 i가 0일 경우에는 그냥 j번째 원소를 바로 리턴한다!

코드 별 차이

맨 위에가 DP를 적용한 경우고 맨 아래는 처음 짠 코드인데 Runtime이 100배 넘게 차이난다. 😎 재밌는 문제였다. 쉽기도 했지만 하하

문제 출처

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