【前缀和】303.区域和检索-数组不可变

Allenlzcoder

于 2024-01-02 22:31:19 发布

阅读量361

点赞数 8

分类专栏： labuladong的算法小抄笔记文章标签：前缀和

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135351740

版权

labuladong的算法小抄笔记专栏收录该内容

78 篇文章

订阅专栏

本文介绍了如何在Java中通过NumArray类实现前缀和算法，包括preSumArray数组的构建和sumRange方法计算指定范围内的和。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

法1：前缀和

class NumArray {
    private int[] preSumArray;

    public NumArray(int[] nums) {
        preSumArray = new int[nums.length + 1];
        for (int i = 1; i < nums.length + 1; ++i) {
            preSumArray[i] = preSumArray[i - 1] + nums[i - 1];
        }
    }
    
    public int sumRange(int left, int right) {
        return preSumArray[right + 1] - preSumArray[left];
    }
}