首页 > 代码库 > Leetcode 303. Range Sum Query - Immutable

Leetcode 303. Range Sum Query - Immutable

2024-08-19 14:37:12   218人阅读

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

 

Note:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

Solution: Because "There are many calls to sumRange Function", we need to put the loop inside the constructor, but not the SumRange() method, otherwise there will be "Time Limit Exceeded" problem.

Dynamic programing to calculate all sums for 0 to nums.Length-1, then if i to j,

return sumAt(j) -sumAt(i-1) when i>0;

return sumAt(j) when i==0;

 1 public class NumArray {
 2     private int[] dp {get;set;}
 3     public NumArray(int[] nums) {
 4         int l = nums.Length;
 5         if(l>0)
 6         {
 7             dp = new int[l];
 8             dp[0]=nums[0];
 9 
10             for(int k=1; k<nums.Length; k++)
11             {
12                 dp[k]=dp[k-1]+nums[k];
13             }
14         }
15         
16     }
17 
18     public int SumRange(int i, int j) {
19         if(i>0)
20         {
21             return dp[j]-dp[i-1];
22         }
23         else
24         return dp[j];
25     }
26 }
27 
28 
29 // Your NumArray object will be instantiated and called as such:
30 // NumArray numArray = new NumArray(nums);
31 // numArray.SumRange(0, 1);
32 // numArray.SumRange(1, 2);

 

Leetcode 303. Range Sum Query - Immutable


联系
我们