当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.303.Range Sum Query Immutable 不变数组的范围和

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


上一篇 LeetCode.066.Plus One 数组加一

下一篇 LeetCode.350.Intersection of Two Arrays II 两数组的交集2

阅读
评论
245
阅读预计1分钟
创建日期 2020-02-09
修改日期 2020-02-09
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论