Leetcode-303: region and retrieval - array immutable

subject

Topic linking

Given an array of integers nums, Handle multiple queries of the following types :

1. Calculation index left and right （ contain left and right） Between nums Elemental and , among left <= right
   Realization NumArray class ：

• NumArray(int[] nums) Using arrays nums Initialize object
• int sumRange(int i, int j) Returns an array of nums Middle index left and right Between elements The sum of the , contain left and right At two o 'clock （ That is to say nums[left] + nums[left + 1] + … + nums[right] )

Example 1：

 Input ：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
 Output ：
[null, 1, -1, -3]

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

Problem solving

Method 1 ： The prefix and

s[i]=nums[0]+nums[1]+....+nums[i-1];
If required nums[2]+nums[3]+nums[4] It only needs
seek s[4]-s[1] that will do .
So you can initialize , Just calculate each s[i] Value

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