Java solution with O(n) space/init and O(1) time for query


  • 1
    M
    public class NumArray {
        public int[] leftSum;
        public int[] rightSum;
        public int total;
        
        public NumArray(int[] nums) {
            int len = nums.length;
            leftSum = new int[len];
            rightSum = new int[len];
            for (int i = 0; i < nums.length; i++) {
                leftSum[i] = total;
                total += nums[i];
            }
            for (int i = nums.length - 2; i >= 0; i--) {
                rightSum[i] = nums[i + 1] + rightSum[i + 1];
            }
        }
    
        public int sumRange(int i, int j) {
            return total - leftSum[i] - rightSum[j];
        }
    }

Log in to reply
 

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