303. Range Sum Query - Immutable.md

303. Range Sum Query - Immutable

Question:

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.

Thinking:

• Method 1:
  • 通过dp，存储从开头加至当前的和。
  • 从a到b的结果就是sum[b + 1] - sum[a]。

class NumArray {
    private int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        sum[0] = 0;
        for(int i = 1; i <= nums.length; i++)
            sum[i] = nums[i - 1] + sum[i - 1];
    }
    public int sumRange(int i, int j) {
        return sum[j+1] - sum[i];
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

Second time

1. Use a 2-D array to save sum from i to j. MLE

class NumArray {
    private int[][]dp;
    public NumArray(int[] nums) {
        int len = nums.length;
        dp = new int[len][len];
        for(int i = 0; i < len; i++){
            for(int j = i; j < len; j++){
                dp[i][j] = nums[j] + (j > 0 ? dp[i][j - 1]: 0);
            }
        }
    }
    public int sumRange(int i, int j) {
        return dp[i][j];
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

2. Use for loop to calculate the result every time.

class NumArray {
    private int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
    }    
    public int sumRange(int i, int j) {
        int sum = 0;
        for(int s = i; s <= j; s++){
            sum += nums[s];
        }
        return sum;
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

3. We only need one dimension array to save the sum of the array up to current position, when we need to calculate sumRange(i, j), we can use sum[j] - sum[i - 1] to get the result;

class NumArray {
    private int[] sum;
    public NumArray(int[] nums) {
        this.sum = new int[nums.length];
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            count += nums[i];
            sum[i] = count;
        }
    }
    public int sumRange(int i, int j) {
        return sum[j] - (i > 0 ? sum[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);
 */

Third time

• Method 1: dp[n]: saves the sum of values up to index n(included).
  • save the sum values.
  • transfer function: dp[i, j] = dp[j] - dp[i] + nums[i]

   class NumArray {
   	private int[] nums = null;
   	private int[] sum = null;
   	public NumArray(int[] nums) {
   		this.nums = nums;
   		int sum = 0;
   		this.sum = new int[nums.length];
   		for(int i = 0; i < nums.length; i++){
   			sum += nums[i];
   			this.sum[i] = sum;
   		}
   	}
   	
   	public int sumRange(int i, int j) {
   		return this.sum[j] - this.sum[i] + this.nums[i];
   	}
   }
  
   /**
    * Your NumArray object will be instantiated and called as such:
    * NumArray obj = new NumArray(nums);
    * int param_1 = obj.sumRange(i,j);
    */