[LeetCode] 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:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

 

这道题让我们检索一个数组的某个区间的所有数字之和,题目中给了两条条件,首先数组内容不会变化,其次有很多的区间和检索。那么我们用传统的遍历相加来求每次区间和检索,十分的不高效,而且无法通过OJ。所以这道题的难点就在于是否能想到来用建立累计直方图的思想来建立一个累计和的数组dp,其中dp[i]表示[0, i]区间的数字之和,那么[i,j]就可以表示为dp[j]-dp[i-1],这里要注意一下当i=0时,直接返回dp[j]即可,参见代码如下:

解法一:

class NumArray {
public:
    NumArray(vector<int> &nums) {
        dp = nums;
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] += dp[i - 1];
        }
    }
    int sumRange(int i, int j) {
        return i == 0? dp[j] : dp[j] - dp[i - 1];
    }
private:
    vector<int> dp;
};

当然,我们也可以通过增加一位dp的长度,来避免在sumRange中检测i是否为0,参见代码如下:

解法二:

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

本文转自博客园Grandyang的博客,原文链接:区域和检索 - 不可变[LeetCode] Range Sum Query - Immutable,如需转载请自行联系原博主。

相关文章
LeetCode 307. Range Sum Query - Mutable
update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。
87 0
LeetCode 307. Range Sum Query - Mutable
LeetCode 304. Range Sum Query 2D - Immutable
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2)。
85 0
LeetCode 304. Range Sum Query 2D - Immutable
|
索引
LeetCode 303. Range Sum Query - Immutable
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
76 0
LeetCode 303. Range Sum Query - Immutable
LeetCode 201. Bitwise AND of Numbers Range
给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。
58 0
LeetCode 201. Bitwise AND of Numbers Range
|
测试技术 索引 Python
LeetCode 303 Range Sum Query - Immutable(范围总和查询-永久不变)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50611359 翻译 给定一个整型数组nums,找出在索引i到j(i小于等于j)之间(包括i和j)的所有元素之和。
786 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词