Simple JAVA solution using Prefix Sum: O(N) space, O(1) lookup time


  • 1
    K

    public class NumArray {

    int[] prefixSum;
    
    public NumArray(int[] nums) {
        int len = nums.length;
        prefixSum = new int[len + 1];
        
        prefixSum[0] = 0;
        for (int i = 0; i < len; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return prefixSum[j + 1] - prefixSum[i];
    }
    

    }


Log in to reply
 

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