【LeetCode】区域和检索 - 数组不可变 Java 题解

HQ数字卡

关注

发布于: 2021 年 03 月 01 日

题目

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象

int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

代码

public class DayCode {    public static void main(String[] args) {        int[] nums = new int[]{1,2,3,4,5};        int i = 1;        int j = 2;        int ans = new NumArray(nums).sumRange(i, j);        System.out.println("ans is " + ans);    }}
/** * https://leetcode-cn.com/problems/range-sum-query-immutable/ */class NumArray {    int[] sums;    public NumArray(int[] nums) {        int n = nums.length;        sums = new int[n + 1];        for (int i = 0; i < n; i++) {            sums[i+1] = sums[i] + nums[i];        }    }
    public int sumRange(int i, int j) {        return sums[j + 1] - sums[i];    }}

复制代码

总结

3 月的每日一题是一道简单题目，题目容易理解。
这个题目的优化方法是前缀和。
前缀和是一种重要的数据预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前 N 项和”
坚持每日一题，加油！

发布于: 2021 年 03 月 01 日阅读数: 16

原文链接:【http://xie.infoq.cn/article/7ff029c5c6c7763bdcd973a48】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】区域和检索 - 数组不可变 Java 题解

题目

代码

总结

HQ数字卡

评论