LeetCode.303.Range Sum Query Immutable 不变数组的范围和

题目描述

303 Range Sum Query - Immutable https://leetcode-cn.com/problems/range-sum-query-immutable/

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note: You may assume that the array does not change. There are many calls to sumRange function.

解题过程

由于数组是不变的，构造函数中初始化累加和到数组 sum 则 sumrange(i,j) = sum[j] - sum[i-1], 特殊处理 i=0 的情况即可

构造函数初始化时间复杂度 O(n) 每次查询时间复杂度 O(1)，空间复杂度 O(n)

private static class NumArray {
    // 累加和
    private int[] sum;

    public NumArray(int[] nums) {
        if (null == nums || nums.length == 0) {
            sum = null;
            return;
        }
        sum = new int[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
    }

    // sum[i->j] = sum[j] - sum[i-1]
    public int sumRange(int i, int j) {
        return sum[j] - (i - 1 >= 0 ? sum[i - 1] : 0);
    }
}

GitHub代码

algorithms/leetcode/leetcode/_303_RangeSumQueryImmutable.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_303_RangeSumQueryImmutable.java