Tuesday, November 10, 2015

LeetCode [303] Range Sum Query - Immutable

 303. Range Sum Query - Immutable

Easy

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
//C++
class NumArray {
    vector<int> sum;
public:
    NumArray(vector<int> &nums) {
        for(auto n:nums){
            sum.push_back(n+(sum.empty()?0:sum.back()));
        }
    }

    int sumRange(int i, int j) {
        return sum[j]-(i==0?0:sum[i-1]);
    }
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

//Java
class NumArray {
    int[] nums;
    public NumArray(int[] nums) {
        int s = 0;
        this.nums = Arrays.copyOf(nums, nums.length);
        for(int i=0; i<nums.length; ++i){
            s += nums[i];
            this.nums[i] = s;
        }
    }
    
    public int sumRange(int i, int j) {
        return this.nums[j] - (i-1>=0?this.nums[i-1]:0);
    }
}

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

No comments:

Post a Comment