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