Java O(1) query and easy understand


  • 1
    J

    Using an int[] sums to store the sums for each index. Then you can only sums[j + 1] - sums[i] when you want to query a certain sum.

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

Log in to reply
 

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