tags: Leetcode easy design prefix sum array python c++

303. Range Sum Query - Immutable

[題目連結:] https://leetcode.com/problems/range-sum-query-immutable/description/

題目:

解題想法:

• 此題為設計實做一個NumArray類別，使用sumRange(i, j) 時要能夠回傳[i, j]範圍內的和

• prefix sum前綴和想法

  • self.nums紀錄原本的數組
  • self.sumArray紀錄從頭到nums[i]的和
  • 最終 self.sumArray[right]-self.sumArray[left]+self.nums[left]即為解
  ​​​​ex:  nums    =[-2, 0, 3, -5, 2, -1]
  ​​​​self.nums    =[-2, 0, 3, -5, 2, -1]
  ​​​​self.sumArray=[-2,-2, 1, -4,-2, -3]
  ​​​​sumRange(2,5)= (-3)-(1)+3= -1
  

Python:

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums=list(nums)
        self.sumArray=list(nums)
        for i in range(1,len(nums)): #prefix sum
            self.sumArray[i]+=self.sumArray[i-1]
        

    def sumRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: int
        """
        return self.sumArray[right]-self.sumArray[left]+self.nums[left]

if __name__ == '__main__':

    result = NumArray(nums= [-2, 0, 3, -5, 2, -1])
    ans = result.sumRange(2, 5)
    print(ans)

C++:

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

private:
    vector<int> copy;
    vector<int> sumArray;
};

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