303.Range Sum Query - Immutable

Posted on | In

Solution 1: TLE

No DP bro. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class NumArray {
  int[] nums;
  public NumArray(int[] nums) {
    this.nums = nums;
  }
  public int sumRange(int i, int j) {
    int sum = 0;
    for(int k = i; k <= j; k++) {
      sum += nums[k];
    }
    return sum;
  }
}

Solution 2: accepted 198ms

DP.
Time: O(n)
Space: O(1) (no extra) 

1
2
3
4
5
6
7
8
9
10
11
12
13
public class NumArray {
  int[] nums;
  public NumArray(int[] nums) {
    this.nums = nums;
    for(int i = 1; i < nums.length; i++) {
      nums[i] += nums[i-1];
    }
  }
  public int sumRange(int i, int j) {
    return (i == 0)? nums[j] : nums[j] - nums[i-1];
  }
}