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

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

📍前言

🕺作者: 迷茫的启明星


学习路线

C语言从0到1

C++初阶

数据结构从0到1

😘欢迎关注:👍点赞🙌收藏✍️留言


🏇码字不易,你的👍点赞🙌收藏❤️关注对我真的很重要,有问题可在评论区提出,感谢阅读!!!


持续更新中~


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

题目概述

给定一个整数数组 nums,实现一个类 NumArray,用于处理以下类型的多个查询:计算索引 left 和 right(包含 left 和 right)之间的 nums 元素的和。其中 left <= right。


题解思路

这个问题可以通过前缀和数组来求解。前缀和数组是一种数据结构,用于在 O(1) 时间复杂度内求解给定区间内的元素之和。前缀和数组的基本思想是将原数组中的元素之和存储在一个新的数组中,使得可以通过简单的数组访问操作来获取区间和。


NumArray 类的实现

首先,定义一个 NumArray 类,包含一个构造函数和一个 sumRange 方法。构造函数接受一个整数数组 nums 作为参数,用于初始化前缀和数组。sumRange 方法接受两个整数 left 和 right 作为参数,用于计算给定区间内的元素和。

class NumArray {
public:
    vector<int> sums;
    NumArray(vector<int>& nums) {
        int n = nums.size();
        sums.resize(n + 1);
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }
    int sumRange(int left, int right) {
        return sums[right + 1] - sums[left];
    }
};



前缀和数组的计算过程

在构造函数中,我们首先计算原数组的长度 n,并将前缀和数组的大小设置为 n + 1。然后,我们遍历原数组,将每个元素累加到前缀和数组中。注意,前缀和数组的第 i 个元素表示原数组的前 i 个元素之和。


求解区间和

sumRange 方法接受两个整数 left 和 right,用于计算给定区间内的元素和。我们可以通过计算前缀和数组中索引 right + 1 和 left 对应的元素之差来求解区间和。这样,我们可以在 O(1) 时间复杂度内完成区间和的计算。


总结

通过使用前缀和数组,我们可以在 O(1) 时间复杂度内求解给定区间内的元素和。这种数据结构在解决区间查询问题时非常有效。在实际应用中,前缀和数组还可以扩展到多维数组,用于求解更高维度的区间问题。


相关文章
|
存储 算法 前端开发
前端算法-删除字符串中的所有相邻重复项
前端算法-删除字符串中的所有相邻重复项
|
8月前
|
人工智能 自然语言处理 算法
【动态规划】【字符串】【前缀和】1639通过给定词典构造目标字符串的方案数
【动态规划】【字符串】【前缀和】1639通过给定词典构造目标字符串的方案数
|
8月前
|
C++ 索引 Python
区域和检索 - 数组不可变(C++)
区域和检索 - 数组不可变(C++)
49 0
|
8月前
|
索引 Python
leetcode-303:区域和检索 - 数组不可变
leetcode-303:区域和检索 - 数组不可变
35 0
|
8月前
|
索引 Python
leetcode-307:区域和检索 - 数组可修改
leetcode-307:区域和检索 - 数组可修改
42 0
|
8月前
|
算法 Java C++
实现一个单词搜索游戏,给定一个二维网格和一个单词列表,找到单词列表中出现在网格中的所有单词(提示:Trie树 + DFS)。
实现一个单词搜索游戏,给定一个二维网格和一个单词列表,找到单词列表中出现在网格中的所有单词(提示:Trie树 + DFS)。
48 0
|
8月前
|
人工智能 算法 数据可视化
【算法训练-数组 五】【数组组合】:下一个排列
【算法训练-数组 五】【数组组合】:下一个排列
60 0
|
算法 索引
【Leetcode】1480. 一维数组的动态和、35. 搜索插入位置
目录 1480. 一维数组的动态和 35. 搜索插入位置
37 0
根据输入的二位数组的行数和列数,动态地为该数组分配存储空间;其次,向二维数组中输入数据;最后输出该数组中的所有原色
根据输入的二位数组的行数和列数,动态地为该数组分配存储空间;其次,向二维数组中输入数据;最后输出该数组中的所有原色

热门文章

最新文章

下一篇
开通oss服务