Java simple O(n) init and O(1) query solution


  • 123
    A

    public class NumArray {

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

    }


  • 0
    P

    nice! it is a simple method.


  • 0
    W

    Same idea, Cpp version :)

    class NumArray {
    private:
        vector<int> sum;
    public:
        NumArray(vector<int> &nums) {   //constructor
        for(int i=0;i<nums.size();i++)
        {
            if(i==0) sum.push_back(nums[i]);
            else
            sum.push_back(sum.back()+nums[i]);
        }
        }
    
        int sumRange(int i, int j) {
            if(i==0) return sum[j];
            return sum[j]-sum[i-1];
        }
    };

  • 0
    S

    Same idea, but I think it's better to check whether i is less than 0 and j is greater than size - 1.

    public class NumArray {
        private int[] sum;
        public NumArray(int[] nums) {
            for(int i = 1; i < nums.length; nums[i] += nums[i - 1], i++);
            this.sum = nums;
        }
    
        public int sumRange(int i, int j) {
            return i - 1 < 0 ? sum[Math.min(j, sum.length - 1)] : sum[Math.min(j, sum.length - 1)] - sum[i - 1];
        }
    }

  • 0
    S
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    Z

    Simplest javascript version using -1 array index:

    var NumArray = function(nums) {
        var length = nums.length;
        var arr = [];
        arr[-1] = 0;
        for(var i = 0;i<length;i++){
           arr[i] = arr[i-1] + nums[i];
        }
        this.arr = arr;
    };
    
    NumArray.prototype.sumRange = function(i, j) {
        return this.arr[j] - this.arr[i-1];
    }

  • 0
    Z

    From the design point of view, should we add "final" for int[] nums, since the array is immutable?


  • 2
    M

    What about overflow


  • 0

    maybe ,but I can't confirm...


  • 0

    Good point, the sum range can be an int, but the total sum can always overflow!


  • 0
    N

    I understand the logic, but where is nums[0] assigned here in construtor?


  • 0
    J

    Good,thank you


  • 0
    Z

    Nice solution. You can also change sumRange() to the version below to make it more concise (they are actually the same):

        public int sumRange(int i, int j) {
            return i == 0 ? this.sums[j] : this.sums[j] - this.sums[i - 1];
        }
    

  • 0
    C

    @metalsolid The return type of sumRange() is an int, so it is guaranteed that the summation is bounded by int.


  • 0
    U

    @wei_fy Very Nice! Your idea is really great


  • 0
    L

    I think this solution changes original array. Maybe we can copy nums[] to a new array instead of using:

    this.nums=nums;
    

  • 0
    K

    @arthur13 It`s quite nice that u have saved space, nearly perfect.


  • 1
    T

    I don't like the idea of changing the input nums array though


  • 0
    T

    @wei_fy hi can u explain y we change the nums array "nums[i] += nums[i - 1];"


Log in to reply
 

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