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:
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
原文：http://www.cnblogs.com/MiaBlog/p/6041347.html