O(n) space complexity and O(1) time complexity for getting sumRange


  • 0
    O
    public class NumArray {
        int[] sumRanges, numbers;
    
        public NumArray(int[] nums) {
            sumRanges = new int[nums.length];
            numbers = new int[nums.length];
            if (nums.length > 0) {
                sumRanges[0] = nums[0];
                numbers[0] = nums[0];
                for(int i = 1; i < nums.length; i++) {
                    sumRanges[i] = sumRanges[i-1] + nums[i];
                    numbers[i] = nums[i];
                }
            }
        }
    
        public int sumRange(int i, int j) {
            if (i == 0) {
                return sumRanges[j];
            } else if (i == j) {
                return numbers[i];
            } else {
                return (sumRanges[j] - sumRanges[i]) + numbers[i];
            }
        }
    }
    

Log in to reply
 

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