Xiaohe-LeetCode 303 Range Sum Query-Immutable

(1)This one I used DP.

O(n).Runtime: 3 ms

This is the only one I have can be accepted on leetcode.

public class NumArray {
　　private int[] acc;//acc[i]:record sum from 0 to i;
　　public NumArray(int[] nums) {
　　　　acc=new int[nums.length+1];
　　　　acc[0]=0;
　　　　for(int i=1;i<=nums.length;i++)
　　　　{
　　　　acc[i]=acc[i-1]+nums[i-1];//transition function
　　　　}
　　　}

　　public int sumRange(int i, int j) {
　　　　return acc[j+1]-acc[i];
　　　　}
}

Xiaohe-LeetCode 303 Range Sum Query-Immutable

原文：http://www.cnblogs.com/CathyXiaohe/p/4985397.html