LeetCode 303. 区域和检索 - 数组不可变

Categories:

题目描述
思路分析
1. 解法一：前缀和（推荐）
相似题目

题目描述

✅ 303. 区域和检索 - 数组不可变

思路分析

解法一：前缀和（推荐）

核心思路：

预处理前缀和数组 pre，pre[i] 表示前 i 个元素的和。

区间和 sumRange(l, r) = pre[r+1] - pre[l]。

复杂度分析：

时间复杂度：初始化 O(n)，查询 O(1)。

空间复杂度：O(n)。

class NumArray {
    private final int[] pre;

    public NumArray(int[] nums) {
        pre = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return pre[right + 1] - pre[left];
    }
}

type NumArray struct {
	pre []int
}

func Constructor(nums []int) NumArray {
	pre := make([]int, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		pre[i+1] = pre[i] + nums[i]
	}
	return NumArray{pre: pre}
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.pre[right+1] - this.pre[left]
}

相似题目

题目	难度	考察点
303. 区域和检索 - 数组不可变	简单	前缀和
304. 二维区域和检索 - 矩阵不可变	中等	前缀和
560. 和为 K 的子数组	中等	前缀和
724. 寻找数组的中心下标	简单	前缀和
238. 除自身以外数组的乘积	中等	前缀积
525. 连续数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/18835470