2 ms Java solution with explaination, O(n) init, O(1) call


  • 1
    M

    sum[i] is the sum before i. (0~i-1). If we want to sum range (i~j), just sum[j+1] - sum[i] .

    public class NumArray {
        int[] sum;
        public NumArray(int[] nums) {
            final int N = nums.length;
            sum = new int[N+1];
            for(int i=1; i<=N; i++){
                sum[i] = sum[i-1] + nums[i-1];
            }
        }
    
        public int sumRange(int i, int j) {
            return sum[j+1] - sum[i];
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.