Simple java solution


  • 1
    Q

    Here is O(n) compute time version without precompute

    public class NumArray {
            int[] nums;
            public NumArray(int[] nums) {
                this.nums=nums;
            }
            public int sumRange(int i, int j) {
                int sum = 0;
                for (int k=i;k<=j;k++){
                    sum = sum+nums[k];
                }
                return sum;
            }
        }
    

    Here is O(1) compute time version with precompute

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

  • 5

    The problem says "There are many calls to sumRange function", let's say the length n of nums[] is one million, and there are one million requests to call sumRange(0, 999,999), each time when the sumRange function gets called, your function needs O(n) time which is time consuming. We can preprocess the nums[] and bring the time complexity of sumRange down to O(1) constant time.


  • 0
    Q

    Yeah, I didn't read the question carefully. Just posted first solution I thought of.


  • 0
    C

    Jeantimex is right, only the second is proper according to the description


  • 0
    Q

    I agree with Jeantimex 100%
    Very important to read directions carefully, otherwise can get tripped by the easiest of questions.


Log in to reply
 

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