Simple Java solution O(1) time, O(n) space


  • 1
    J
    /**
     * Use map to save sum[i] (0 <= i <= n) in pair (i, sum[i]).
     * whereas sum[i] = nums[0] + .. + nums[i-1].
     * So, we can get the range in constant time:
     *     range(i, j) = sum[j+1] - sum[i];
     *
     */
    
    public class NumArray {
    private Map<Integer, Integer> map;
    
    public NumArray(int[] nums) {
        map = new HashMap<>();
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
        	map.put(i, sum);
        	sum += nums[i];
        }
        map.put(nums.length, sum);
        return;
    }
    
    public int sumRange(int i, int j) {
        return map.get(j + 1) - map.get(i);
    } }

Log in to reply
 

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